CALM: when coordination is necessary

Where do the steps that need coordination cluster?

CALM: the theorem behind the right-algebra rule

Hellerstein's conjecture, proved by Ameloot, Neven and Van den Bussche: a program has a consistent, coordination-free distributed implementation if and only if it is monotone.

Monotone means: adding facts never retracts a conclusion. Selection, projection, join and union are monotone. Negation, aggregation, counting, NOT EXISTS, set difference and "the maximum" are not.

This upgrades the right-algebra rule from a pattern to a necessity. Commutativity, associativity and idempotence are the algebraic signature of monotone computation over a join-semilattice. CALM says that signature is not merely sufficient for coordination-freedom, it is required. Coordination is needed precisely at non-monotone steps. That is why every distributed system's coordination points cluster in the same five places:

1. Uniqueness checks (a negation: "no other row has this name").
2. Aggregation barriers (a count must know that it is complete).
3. Sequencing (a maximum).
4. Termination detection.
5. Garbage collection.

The last one closes a loop from Sessions, convergence and quorums. We argued from mechanism that CRDT tombstone collection needs global knowledge. CALM says why it was forced: "nobody still references this" is a negation, therefore non-monotone, therefore coordination is mandatory. The collector was never going to be free. The same reading explains watermarks in stream processing (a coordination device that makes a non-monotone aggregation safe to emit), BSP barriers (the global "wait for everyone" steps of bulk-synchronous computation), and "seal the partition" in table-format commits. Each is a monotonicity violation with a coordination patch.

CALM converts "do we need coordination here?" from an architecture opinion into a question with a mechanical answer: does this computation ever retract something it previously emitted?