CALM Theorem

The CALM theorem, "Consistency as Logical Monotonicity", states that a program has a consistent, coordination-free distributed implementation if and only if it can be expressed in monotonic logic.

Monotonicity means that adding new input facts cannot invalidate conclusions already produced. If a computation only accumulates information, then replicas can process messages in different orders, at different times, and with partial local knowledge while still converging without synchronous coordination.

Non-monotonic computation depends on absence, exclusion, negation, exact completeness, or globally current knowledge. Those decisions usually require coordination, a narrower ownership boundary, a reservation or escrow scheme, a pending state, or a weaker domain promise.

In Cohesive terms, CALM gives a test for coordination avoidance:

• Monotone transitions, projections, and merge rules can often be implemented with asynchronous delivery and eventual convergence.
• Non-monotone invariants require some mechanism that establishes enough completeness or exclusion before the decision is exposed.
• CRDTs are one realization family for monotone replicated state, but CALM applies at the program and observation level, not only at the data type level.
• Weak Isolation Patterns often work by making non-monotonicity explicit through versions, reservations, pending states, compensation, reconciliation, or scoped coordination.

CALM is therefore not a replacement for consistency models. It explains when a useful consistency guarantee can be obtained without coordination, and when coordination or model redesign is required.

Like the asynchronous computability theorem, CALM is a computability-oriented constraint on distributed design. CALM uses logical monotonicity to characterize when coordination can be avoided; ACT uses topology to characterize when wait-free tasks can be solved.

External References

• Joseph M. Hellerstein and Peter Alvaro, Keeping CALM: When Distributed Consistency Is Easy, arXiv, 2019; Communications of the ACM, 63(9):72-81, 2020. DOI
• Peter Alvaro, Neil Conway, Joseph M. Hellerstein, and William R. Marczak, Consistency Analysis in Bloom: a CALM and Collected Approach, CIDR 2011.

Related concepts: coordination, consistency models, safety and liveness, asynchronous computability theorem, ordering, delivery semantics, weak isolation patterns, CRDTs, invariants, projections, observation, compositionality, universal constructions.