In Favor of Monotony in a Complex WorldDaily WisdomBlockedUnblockFollowFollowingApr 3Coordination seems to be a magical word for today’s digital age as given the proliferation of various collaboration tools, coordination seems never have been so easy.
Yet, when it comes to high performing scalable distributed systems, coordination might be a barrier.
Based on the Universal Scalability Law, the need for coordinating things should be avoided as this would make the overall process flow to get simpler and faster.
Yet, is there a way to know when to avoid coordination?According to Brooks, there is a distinction between ‘essential complexity and accidental complexity’ as he asserted in his ‘No silver bullet’ essay.
In a similar vein, there can be essential coordination, which could not be provided without coordinating, and accidental coordination, which could have been avoided with a more careful design.
In general, rather than being a necessary evil, coordination should be seen as an incidental requirement of a design decision.
A major reason why accidental coordination occurs is the common preoccupation among software engineers with trying to solve consistency questions at lower levels of the stack using storage semantics rather than using the application level semantics.
Although the lower layers might be significant, focusing only on them could not unlock the potential.
As Pat Helland asserted in ‘Building on quicksand’, writes don’t commute, but application-level operations can.
The main question to be asked should be: “What is the category of problems that can be consistently computed in a distributed way without a need for coordination, and what problems lie outside this category?”Monotonicity: Monotonic systems only move in one direction and once something is learned to be true no additional information can then refute the fact.
A monotonic deadlock detection such as in the following graph would be an example of such a system.
During the exchange of information among the machines regarding the edges at some point, the cycle regarding and will become apparent which could not be avoided regardless of other edges to be discovered.
Another example would be in the case of unreachability.
When a specific object is unreachable, it would not count as being monotonic as the next edge to be uncovered could make it reachable.
While in the first example, the question is about “Does there exist?” ( ), in the second case, the question is about “Does not exist?” ( ).
If the interest would be in reachability rather than unreachability, that would be monotonic due to the fact that once an object is known as being reachable, finding out it is also reachable via a second path would change nothing unless within the system objects and edges could be deleted.
The gist in these examples is that the property which is required for these conclusions to be made on partial information continue to hold in case of availability of full information.
This concept of monotonicity is one of the crucial aspects of the CALM Theorem (Consistency as Logical Monotonicity) according to which a program has a consistent, coordination-free distributed implementation if and only if it is monotonic.
According to this theorem, the line between what is possible (‘if’ part) and what is impossible (the ‘only if’ part) can be drawn.
Interestingly, the famous poster message “Keep CALM and Carry On” is also based on this concept in the sense that if one keeps things calm then he is always in a position to ‘carry on’ without a need for stopping and coordinating.
Once the CALM theorem has been understood, the following questions might be asked: “What is the category of problems to be computed in a monotonic fashion, and what problems lie outside that category?” In addition to the concepts of coordination and consistency terms such as commutative and confluent might need to be introduced in order to find an answer.
A binary operation is said to be commutative if the order of its operand does not change the output.
To give an example, while the addition operation is commutative, the subtraction operation isn’t.
In a similar vein, confluence occurs if an operation produces the same sets of results for any non-deterministic ordering and batching of a set of inputs.
If the results of one confluent operation are consumed by another, the resulting composite operation is confluent.
Therefore, confluence can be implemented in the case of individual operations, or even entire distributed programs.
Confluent operations lie at the core of monotonic systems.
In order to deal with operations about negation such as deletions, a separate set of deletions can be maintained alongside the operations of additions.
In terms of relational algebra, there can be projection or selection, but not set-difference.
In terms of changeable state there can be inserts, but not deletes or updates.
One of the major insights in CALM is its emphasis on consistency in terms of program outcomes rather than the traditional histories of storage updates.
Shifting the focus from implementation to specification enables one to ask questions about what computations are possible.
In order to make use of monotonic programming patterns within a context of functional programming, an object-oriented framework is required to avoid bare assignments to changeable variables.
While immutability provides a monotonic pattern, mutability does not.
If there is no monotonic implementation for every application feature, it might be useful to coordinate the critical path.
One option would be that an application runs in the background.
Another option would be to continue without coordination, yet establish a mechanism to discover if there is an inconsistency so that the application can “apologize”.
By using the CALM Theorem, the frontier of the possible can be delineated as it shows that monotonicity being a property of a program implies consistency as the result’s property.
At the same time, the reverse also holds true; to ensure consistent execution there is runtime enforcement (coordination) for non-monotonic programs.
As a program property, CALM shows how reasoning by use of static program analysis, and limits the use of runtime checks.
As it is the case with every aspect of life, merely using buzzwords such as collaboration or cooperation would do no magical tricks unless we gain awareness on how to delineate the line for making something probable and possible.
RelatedcommentsOriginally published at www.
datadriveninvestor.
com on April 3, 2019.
.