Symptom

Every distributed result so far has been a prohibition. Two Generals: no agreement over a lossy channel. FLP: no deterministic asynchronous consensus. Byzantine: not below $3f+1$. CAP: not all three.

So you conclude coordination is unavoidable and reach for a consensus service. Now every increment of a counter is a Raft round trip, your throughput is capped by one leader’s fsync rate, and a regional outage stalls writes that had no business needing global agreement in the first place.

The concrete version: you are building a collaborative editor, or a shopping cart, or a set of feature flags, or a like counter. None of these have a meaningful notion of “the one true order of operations.” Two users adding different items to a cart do not conflict in any way a customer would recognize. Yet you have serialized them through a leader, because the theorems said you had to, and the theorems did not say that.

Statement

CALM: Consistency As Logical Monotonicity. A program has a coordination-free, eventually consistent distributed implementation if and only if it is monotone.

Let a distributed program compute an output as a function of a growing input set. The program is monotone if its output set only grows as its input set grows: for inputs $I \subseteq I’$, $P(I) \subseteq P(I’)$. CALM (Hellerstein 2010, proved by Ameloot, Neven, and Van den Bussche 2013 via a relational-transducer-network argument) states that $P$ is computable by a coordination-free distributed implementation iff $P$ is monotone. The proof of the hard direction shows that a non-monotone program must, in some execution, retract an output it has already emitted, which requires knowing that no further input is coming, which requires coordination.

This is the only iff among the distributed results, and it is what makes it a design tool rather than a warning. It does not merely say monotone programs are easy. It says monotonicity is precisely the boundary, so if your program needs coordination there is a non-monotone step in it, and finding that step tells you exactly where the cost is and often how to remove it.

CRDTs are the data-structure half of the same idea. A Conflict-free Replicated Data Type is a value whose merge operation is associative, commutative, and idempotent — a join semilattice. Replicas that have seen the same set of updates, in any order, with any duplicates, reach the same state. That is monotonicity made concrete in a type.

Argument

Why monotone means coordination-free. If output only grows, a replica that emits a fact never has to take it back. Any fact it has learned is permanent, and any fact it has not yet learned will only add to what it knows. So it can answer immediately with what it has, and correctness is a matter of eventual delivery rather than ordered delivery. Nothing needs to be agreed before anything is done.

Why non-monotone means coordination is required. Consider NOT EXISTS, or COUNT, or “the minimum bid wins.” To emit “no record matches,” a node must know that no record matching will ever arrive. That is a statement about the future and about other nodes, and there is no way to establish it locally. So the node must wait for a barrier: everyone confirms they are done. That barrier is coordination, and it is unavoidable because it is doing genuinely necessary work.

The dividing line is remarkably close to the one in logic. Monotone programs are those expressible with selection, projection, join, union, and recursion — the positive fragment. Add negation or aggregation and you leave the class. A distributed program’s coordination cost is legible from its syntax, which is the practical payoff and the reason the Bloom language exists: its type checker flags the non-monotone points and tells you where you will need a barrier.

The two CRDT families. State-based (CvRDT) replicas ship their whole state and merge with a join; convergence needs only that the merge is a semilattice join, so the network may reorder, duplicate, and delay freely. Operation-based (CmRDT) replicas ship operations and require exactly-once causal delivery, in exchange for far less bandwidth. They are equivalent in expressiveness and the choice is an engineering one about message size versus delivery guarantees.

A worked example: the G-Counter. A counter that only increments, replicated across $n$ nodes, is a vector of per-node counts. Node $i$ increments only slot $i$. Merge is element-wise maximum, and the value is the sum.

Element-wise max is associative, commutative, and idempotent, so replicas converge under any delivery order. With three nodes at states $[3,1,0]$, $[3,4,0]$, $[0,1,7]$, the merge of all three is $[3,4,7]$ giving 14, and merging in any other order or re-merging any pair again gives the same vector. The idempotence is what makes retries safe, which is why a CRDT tolerates an at-least-once network with no deduplication layer.

The PN-Counter, which supports decrement, is two G-Counters — one for increments, one for decrements — with the value as the difference. Note what happened: a non-monotone operation was expressed as the difference of two monotone ones. That move, pushing the non-monotonicity into the read rather than the write, is the main technique in CRDT design.

Where it stops. A counter with a lower bound — inventory that may not go below zero — is not a CRDT and cannot be made into one. Enforcing the bound requires knowing the global total, which is exactly the non-monotone barrier. Real systems solve this by escrow: partition the 100 available units into 20 per replica, let each spend its allocation coordination-free, and coordinate only to rebalance or when a replica exhausts its share. Coordination has not been eliminated; it has been moved off the common path and made rare, which is what CALM tells you to look for once you know the operation is non-monotone.

Forbids

Coordination-free implementation of any non-monotone operation. Distributed COUNT with a threshold, “is this set empty,” global uniqueness constraints, and “assign the next sequential ID” all require a barrier. No CRDT design removes it, and time spent looking for one is wasted.

A CRDT for a bounded resource. Inventory that cannot oversell, a bank account that cannot overdraw, seat reservation without double-booking. The bound is the non-monotone step.

Unique constraint enforcement without coordination. Two replicas can accept the same username simultaneously. Any system claiming uniqueness with no coordination is either coordinating somewhere you have not looked, or is not enforcing uniqueness.

Convergence from a merge that is not idempotent. A merge that adds rather than joins double-counts on redelivery, and networks redeliver. This is the most common bug in hand-rolled “CRDTs.”

Does not forbid

It does not forbid strong consistency where you need it. The point is locating it, not avoiding it. A well-designed system runs the monotone 95% coordination-free and spends its coordination budget on the rest. Amazon’s shopping cart is the canonical case: adds are monotone and always available, removals are handled as an add-set and a remove-set, and the rare anomaly of a deleted item reappearing was judged better than an unavailable cart.

It does not mean CRDTs are only for toy data. Automerge and Yjs implement full collaborative rich-text editing as CRDTs; Redis Enterprise ships CRDT types for geo-distributed deployments; Riak shipped counters, sets, and maps; Figma and Linear are built on this class of technique. The RGA and Logoot families solve ordered-sequence convergence, which was long assumed to need operational transformation and a central server.

It does not require giving up transactions. Read-Atomic and other coordination-avoiding isolation levels give useful atomicity guarantees without serialization, and the RAMP protocols show a genuine middle ground rather than a compromise between two extremes.

It does not say monotone programs are trivially correct. They converge, which is a statement about state, not about usefulness. A text CRDT can converge to an interleaved mess that no user typed. Convergence is necessary and nowhere near sufficient, and the hard part of Automerge and Yjs is intention preservation, not convergence.

It does not mean coordination is slow everywhere. Within a single rack, consensus costs microseconds. CALM matters when coordination is expensive, which means geographically distributed or offline-capable systems, and applying it zealously inside one datacenter optimizes something that was not the bottleneck.

Boundary

  • Eventual, not immediate. CALM guarantees replicas converge once they see the same updates. It says nothing about how long divergence lasts, and a partitioned replica can serve stale reads indefinitely.
  • Metadata growth. CRDTs remember more than their value. Tombstones for deleted elements, causal contexts, per-replica vectors: an OR-Set that has had a million elements added and removed can carry a million tombstones. Delta CRDTs and garbage-collection protocols mitigate this and none eliminate it, and this is the practical reason CRDTs are not the default everywhere.
  • The monotone framing must be found. Most useful operations are not syntactically monotone but have a monotone reformulation, and finding it is design work with no procedure. PN-Counters and escrow are examples of the reformulation succeeding; unique-username is an example of it failing.
  • Invariant confluence. Bailis’s I-confluence gives the complementary criterion for transactional invariants: an invariant can be maintained coordination-free iff it is preserved under merge of any two valid states. Foreign keys pass, uniqueness fails, and the check is mechanical.

The reframe worth keeping: the impossibility results tell you what cannot be done with arbitrary programs. CALM tells you which programs they apply to. Most of what a system does every second is on the free side of that line, and the work is in noticing which parts are not.