I love this work. I might claim it (and some of its antecedents) is the most important distributed systems work of the last decade.
Why? It addresses the central question in distributed (and multi-threaded!) system design: when do we need to coordinate between systems? This is important for exactly the reason that the James Hamilton quote says. Successful scalability requires avoiding coordination. Scalable systems (and efficient systems, and fast systems) are the ones that minimize scalability to the level absolutely required by the guarantees they want to offer.
As the authors say:
> As system builders, of course, we are interested in the complement of this space: what can be achieved, and, importantly, how can we achieve it while minimizing complexity and
cost? The CALM Theorem presents a positive result that delineates the frontier of the possible.
This tool for thinking about what possible systems we can build is one that's very understandable to most programmers:
> A program P is monotonic if for any input sets S,T where S ⊆ T, P(S) ⊆ P(T).
A program is monotonic if, when you run it on a subset of its inputs, you get a subset of its outputs. As you run it on more data, the set of true things may grow, but it never shrinks.
> A program has a consistent, coordination-free distributed implementation if and only if it is monotonic.
Now we have a useful roadmap to designing scalable distributed system, fault tolerant distributed systems, scalable parallel compute code, and fast multi-threaded code. Using the definition we can identify whether a program is monotonic, and if it is we know we can implement it without coordination. If it is not, we can decompose a program into monotonic and non-monotonic parts, and (if all goes well) take advantage of the non-monotonicity. In many cases, we can do tons of parallel work and only coordinate a couple times.
> Conflict-free replicated data types (CRDTs) provide an object-
oriented framework for monotonic programming
More conceptual clarity! CRDTs are widely used, and widely talked about. Why do they work? Because they provide ADTs for writing monotonic programs.
> A program P is monotonic if for any input sets S,T where S ⊆ T, P(S) ⊆ P(T).
> A program is monotonic if, when you run it on a subset of its inputs, you get a subset of its outputs. As you run it on more data, the set of true things may grow, but it never shrinks.
Yeah, this framework seems powerful.
Something I find interesting is that you can get monotonic (and therefore coordination-free) relaxations of arbitrary problems. In extremis, you can derive a relaxed version P' thus
P'(S) = {<s, P(s)> | s ⊆ S}
and now
P'(S) ⊆ P'(T) if S ⊆ T for _any_ (well defined) P
This seems tautological but in some cases a relaxed version is good enough: it gives you convergence and eventual consistency in a coordination-free setting, at the cost of maybe having to roll back some results. And when it doesn't, it gives you a coherent model of what to make of the situation until coordination yields a definitive answer.
But that was like last week, haven't really put this in practice yet.
In those examples what is being processed are partially-ordered operational logs, but it's essentially the same (just that whenever S ⊆ T there, what you're seeing is an extension of an op log, which is a bit more intuitive).
This boils down to materalizing every possible nondeterministic outcome.
I wouldn't call anything that involves a power set with 2^n space complexity "relaxed" tbh ^^'.
While I do agree with the general sentiment, I do still think that going with states that can be reconciled/merged is a more realistic approach, than just wildy diverging.
The logic for taming unbounded nondeterminism has been around for decades though. As Dijkstra and Scholten admit, it’s basically just applied lattice theory.
In fact, at a glance, this paper appears to be building on that foundation. It’s not hard to see how monotonicity makes reasoning about nondeterminism considerably more manageable!
Did you read the remark at the end of my comment? In the practical cases I was exploring, that combinatorial explosion does not happen. It's relaxed in the sense that it is coordination-free.
This is a cool result from a couple of famous database experts. Though, it seems that the only set of practical programs that satisfy the CALM property are set-based operations found in database systems. These are expressive, but not expressive enough to cover all possible computations. So, is it the case that all computations can be decomposed into a partial order of CALM programs each of which don’t need coordination except at the points of order. If so, is this approach analogous to Lamport’s CStructs in Generalized Consensus?
Examples of monotonic computation that fit are traditional database operators: filters, projections, joins. Interestingly enough, there is some coordination needed for joins, i.e. the items that match need to be in the same place at some point. But, that's not the type of coordination that the paper is pushing back against. It's still possible to distribute the computation without worrying about ordering.
Examples on non-monotonic computation (i.e. that don't fit) include aggregations, in particular those that include time series with windows. The answer depends on what is in the window. So, if you take an average and only include a subset of the data in a window, the output will change when you add more data in the window. At least, that's how I interpret the monotonic requirement.
the authors postulate that not all computations (programs) should require global coordination.
if you compartmentalize data in such a way, that most of your computations are done locally on a node (with the data that can fit a single node) - then you don't need global coordination.
for example, if you have two nodes: one in the US and one in the EU, and all customer data is stored in the corresponding geo region => you dont need global coordination. EU users and all their related computations can be perfectly done without coordinating with US node.
US node => serves US customers and all compute done locally. same logic applies to EU node, and Asia node.
for a subset of computations that require global consensus you can either broadcast shared data to regions, and do some sort of scatter/gather, map/reduce
but partitioning by geo is one of the many possible ways, there could be many other ways to partition your global working set in a way to minimize global coordination.
I call this "many small worlds" approach, where each small world can fit a single node and does not need global coordination.
Contrast it to "a single large world" - where you have a planet-scale globally distributed, replicated system with a consensus. You spend a lot of resources on duplication, and coordination, and end up wasting the 80% capabilities of this system by storing the data that could be perfectly served from a single cheap EC2 host.
even for computation that require global coordination, let's say you need to calc global AVG():
you can rewrite it in scatter/gather algorithm by splitting it into 1) TotalSum and 2) TotalCount
scatter this across node, compute locally, gather results (2 fields per node) and compute global average.
a lot of global consensus algos can be rewritten in scatter/gather manner to parallelize and offload work to nodes without global synchronization
I remember seeing a blip of this when it came out, but I haven't heard anything since. Anyone know if it's known / used / ??, or has it been subsumed by some other thing?
They seem to be iterating on this (or less graciously dumping something and moving on). The latest thing seems to be called hydro https://github.com/hydro-project
I think it's logically monotonic in the sense that as you add input data to your query, the output simply accumulates (you never have to retract any prior conclusions).
Consistency between two accumulators is easy, they just sum their states.
any non-monotonic computation can be split into monotonic, where they process the bulk of the data, and folding the results to product the final result
Min is also logically monotonic in the same sense though, right? As a min accumulator I can throw away all past information once I've computed my result and never have consistency issues in light of new data.
A better example would be reachability analysis in a DAG - here you really do have monotonicity failure when merging results from multiple workers.
Why? It addresses the central question in distributed (and multi-threaded!) system design: when do we need to coordinate between systems? This is important for exactly the reason that the James Hamilton quote says. Successful scalability requires avoiding coordination. Scalable systems (and efficient systems, and fast systems) are the ones that minimize scalability to the level absolutely required by the guarantees they want to offer.
As the authors say:
> As system builders, of course, we are interested in the complement of this space: what can be achieved, and, importantly, how can we achieve it while minimizing complexity and cost? The CALM Theorem presents a positive result that delineates the frontier of the possible.
This tool for thinking about what possible systems we can build is one that's very understandable to most programmers:
> A program P is monotonic if for any input sets S,T where S ⊆ T, P(S) ⊆ P(T).
A program is monotonic if, when you run it on a subset of its inputs, you get a subset of its outputs. As you run it on more data, the set of true things may grow, but it never shrinks.
> A program has a consistent, coordination-free distributed implementation if and only if it is monotonic.
Now we have a useful roadmap to designing scalable distributed system, fault tolerant distributed systems, scalable parallel compute code, and fast multi-threaded code. Using the definition we can identify whether a program is monotonic, and if it is we know we can implement it without coordination. If it is not, we can decompose a program into monotonic and non-monotonic parts, and (if all goes well) take advantage of the non-monotonicity. In many cases, we can do tons of parallel work and only coordinate a couple times.
> Conflict-free replicated data types (CRDTs) provide an object- oriented framework for monotonic programming
More conceptual clarity! CRDTs are widely used, and widely talked about. Why do they work? Because they provide ADTs for writing monotonic programs.