Coordination Avoidance

The design discipline of eliminating synchronisation (locks, quorums, consensus rounds) wherever a computation can be proved correct without it. The CALM Theorem makes this precise: coordination is avoidable exactly for monotonic programs.

Practical techniques:

Build from monotonic primitives (CRDTs, set unions, counters-up-only)
Use Immutable Data Structures and Tombstones to convert mutation into monotonic history
Isolate the non-monotonic boundary (e.g. a shopping-cart checkout) and coordinate there only
Program in a language like Bloom Language that makes monotonicity syntactically checkable

Contrasts with storage-consistency work (linearizability, serializability) which enforces coordination inside the storage layer regardless of program shape.

In this vault

Backlinks

Tombstones line 10
Immutable Data Structures line 10
Bloom Language line 12
CAP Theorem line 11
CALM Theorem line 22
Keeping CALM - When Distributed Consistency is Easy line 41
Keeping CALM - When Distributed Consistency is Easy line 26
Keeping CALM - When Distributed Consistency is Easy line 15
Monotonic Logic line 15
Confluence line 11
CRDTs line 17

Linked Pages

Gossip-Based Computation of Aggregate Information

Reference: David Kempe, Alin Dobra, Johannes Gehrke (2003). FOCS 2003 (IEEE Symposium on Foundations of Computer Science). Source file: focs2003-gossip.pdf. URL

Summary

This paper analyzes simple gossip protocols (epidemic-style, randomized pairwise exchanges) for computing aggregate functions — sums, averages, quantiles, random samples — over values held by nodes in highly dynamic distributed systems like P2P networks and sensor networks. The key contribution is the Push-Sum protocol, which distributes weight alongside value so that the ratio stored at each node converges exponentially fast to the true average, even in the face of node failures and message loss.

The second contribution is a precise diffusion speed formalism linking protocol convergence to random walk / Markov chain mixing times, letting the authors analyze uniform gossip, flooding, and other mechanisms uniformly. Push-Sum converges in O(log n + log 1/ε + log 1/δ) rounds with exponentially small message sizes, making it suitable for massive, volatile networks.

Key Ideas

Push-Sum: maintain (value, weight) pairs, exchange halves with random peer; ratio converges to global average.
Mass conservation invariant underlies correctness.
Diffusion speed = convergence rate, mapped to Markov chain mixing times.
Robust to node/link failures — degraded guarantee scales with 1/(1-µ)^2.
Extends to sums, quantiles, random samples, and arbitrary linear syntactic aggregates.

Connections

Gossip Protocols
Multi-Agent Systems
Self-Adaptive Systems
Peer Sampling Service
Large Population Models
CALM Theorem — mass-conservation aggregation is the canonical monotonic primitive
Keeping CALM - When Distributed Consistency is Easy
Monotonic Logic

Conceptual Contribution

Claim: Aggregates (sums, averages, quantiles, random samples) over a massive, volatile network can be computed by simple gossip protocols that converge exponentially fast; a mass-conservation trick (Push-Sum) gives precise averages with only local pairwise exchange.
Mechanism: Introduces Push-Sum (each node maintains a (value, weight) pair and halves on exchange; ratio = average), generalises it to Push-Vector and Push-Synopses for linear synopses; defines diffusion speed connecting protocol convergence to random-walk mixing times on the communication graph; proves O(log n + log 1/ε + log 1/δ) convergence with robustness under message loss and node failure.
Concepts introduced/used: Push-Sum, Mass Conservation, Diffusion Speed, Uniform Gossip, Flooding, Push-Synopses, Random Walks on Graphs, Aggregate Functions
Stance: formal-semantic / foundational (for gossip-based distributed algorithms)
Relates to: Theoretical foundation for Gossip-based Aggregation in Large Dynamic Networks (which re-derives Push-Sum empirically as averaging) and underpins the aggregation primitives surveyed in Gossiping in Distributed Systems and Gossip Protocols; gossip training in Edge Intelligence Survey inherits this analysis.

In this vault

CAP Theorem

Brewer (2000); proved Gilbert & Lynch (2002). A replicated storage system cannot simultaneously provide all three of: Consistency (linearizable reads), Availability (every request gets a response), Partition tolerance (continues operating under network partitions). Under a partition, the system must choose between C and A.

CAP is a negative result about storage. The CALM Theorem is its positive counterpart about programs: the subclass of programs achieving all three is exactly the monotonic ones.

In this vault

CRDTs

Conflict-free Replicated Data Types (Shapiro et al.) — data types whose operations commute, associate, and are idempotent, guaranteeing that replicas updated in any order converge to the same value. Each CRDT is an object-oriented packaging of a small monotonic state-merge lattice.

From the CALM Theorem viewpoint, CRDTs are canonical monotonic building blocks: programs that stay within the CRDT abstraction are automatically coordination-free. They express a partial monotonic pattern — for end-to-end application consistency the program’s composition of CRDTs also has to stay monotonic, which is the standing open problem the CALM paper highlights.

Common examples

G-Counter, PN-Counter
G-Set, 2P-Set, OR-Set, LWW-Set
LWW-Register, MV-Register
RGA (sequence CRDTs)

In this vault

Confluence

Program consistency (as used by CALM): a distributed program is confluent if it produces the same observable outputs regardless of the non-deterministic order in which its inputs are delivered or batched. Formally, a confluent single-machine operation is one that maps sets of inputs to sets of outputs such that repeated or reordered applications yield the same final set.

Confluence is weaker and more permissive than storage-level linearizability / serializability — it allows wildly different mid-flight states across replicas as long as the application-level outcome converges. This is the user-observable criterion the CALM Theorem characterises.

In this vault

Monotonic Logic

A logic in which the conclusion set grows monotonically with the premise set: adding information never retracts a conclusion. Formally, a program P is monotone if S ⊆ T ⟹ P(S) ⊆ P(T).

Monotone relational operations: selection, projection, intersection, join, transitive closure. Non-monotone: universal quantification, set difference, aggregates with totality assumption, Negation as Failure.

In distributed systems, monotonicity is the load-bearing property behind the CALM Theorem: monotone programs are safe under arbitrary message reordering and partial delivery, because no conclusion ever has to be taken back.

In this vault

Keeping CALM - When Distributed Consistency is Easy

Keeping CALM: When Distributed Consistency is Easy

Reference: Joseph M. Hellerstein & Peter Alvaro (2019). arXiv:1901.01930v2. Source file: ../1901.01930v2.pdf (in parent directory). URL

Summary

An accessible, updated statement of the CALM Theorem — Consistency As Logical Monotonicity: a program has a consistent, coordination-free distributed implementation if and only if it is monotonic in a formal logical sense. Monotonic programs are “safe” under missing information and can proceed without waiting: once something has been concluded, it stays concluded. Non-monotonic programs (“change their mind” in the face of new inputs) are necessarily order-sensitive and therefore require coordination to produce a single deterministic outcome.

CALM is a positive counterpart to the negative results of the CAP Theorem and the FLP impossibility. Where CAP says “you can’t always have it all”, CALM delineates the class of programs that can in fact satisfy all of C, A, and P simultaneously: exactly the monotonic ones. The theorem shifts attention away from storage consistency (linearizability, serializability) toward program consistency — Confluence: deterministic outcomes despite non-deterministic message delivery and ordering.

The paper traces the theorem’s implications for Bloom Language, Dedalus, CRDTs, coordination-free design patterns (monotonic accumulation, tombstones, immutable data), distributed garbage collection, and Amazon’s shopping-cart example. It closes with open questions: expressiveness of monotonic languages, program synthesis targeting monotonicity, repair of non-monotonic code, and a possible Stochastic CALM for near-optimum stochastic algorithms.

Key Ideas

Monotonicity ⇔ coordination-freeness ⇔ consistency (CALM)
Program consistency = confluence: same outputs regardless of message order / batching
Non-monotonic operations retract earlier conclusions, hence must wait for “all the news” — requiring Coordination Avoidance logic to know when
Formalisation via Relational Transducer networks (Ameloot, Neven, Van den Bussche)
CAP is a special case: linearizable storage is one non-monotonic operation; CALM asks the question across all programs
Practical playbook: immutable data structures, tombstones, set-monotonic accumulation, CRDTs as object-oriented monotonic types
Bloom gives syntactic monotonicity checking — a programmer writing monotonic Bloom is guaranteed coordination-free correctness

Connections

Conceptual Contribution

Claim: A distributed program is consistent and coordination-free iff it is expressible in monotonic logic — a tight, provable characterisation that converts “distributed consistency is hard” into a precise question about a program’s logical shape.
Mechanism: Formalise programs as networks of Relational Transducers (Ameloot et al.); define Confluence as program-level determinism under non-deterministic delivery; prove biconditional between confluence and monotonic-logic expressibility.
Concepts introduced/used: Monotonic Logic, Confluence, Coordination Avoidance, Relational Transducer, Bloom Language, Dedalus, CRDTs, CAP Theorem, Immutable Data Structures, Tombstones, Stochastic CALM
Stance: foundational / survey
Relates to: Provides the theoretical companion to the Gossip Protocols cluster (Gossip-Based Computation of Aggregate Information, Gossip-based Aggregation in Large Dynamic Networks) — gossip aggregation with mass conservation is exactly a monotonic accumulation, hence coordination-free. Frames why Extensible Distributed Coordination must reach for stored-procedure coordination precisely where programs are non-monotonic. Contrasts with Are Multiagent Systems Resilient to Communication Failures: that paper shows game-theoretic MAS are brittle under message loss — CALM identifies the logical class of programs immune to such loss. The monotonic/non-monotonic split echoes Foundations of Logic Programming - Lloyd’s distinction between Horn-clause logic and Negation as Failure.

CALM Theorem

Consistency As Logical Monotonicity (Hellerstein 2010 conjecture; Ameloot, Neven, Van den Bussche 2013 proof). A distributed program has a consistent, coordination-free implementation if and only if it is expressible in monotonic logic.

Monotonic programs produce a set of outputs that only grows as inputs arrive (S ⊆ T ⟹ P(S) ⊆ P(T)). Such programs are safe under missing information: any conclusion reached on a subset of inputs remains valid when more arrive. Non-monotonic programs may retract earlier conclusions, so they must wait for “all the news” — which is what distributed coordination enforces.

CALM is the positive counterpart to the CAP Theorem: it names the exact class of programs that can satisfy Consistency, Availability, and Partition-tolerance simultaneously.

Why it matters

Moves consistency from a property of storage (linearizability, serializability) to a property of programs — Confluence.
Tells programmers what kinds of features are free (monotonic: set union, counting up, set-containment) and what must be paid for (non-monotonic: set difference, strict aggregation, count-exact, deletions without tombstones).
Gives a design rule for coordination-free systems: build from monotonic primitives — CRDTs, Immutable Data Structures, Tombstones, monotonic accumulators — and only add coordination at non-monotonic boundaries.

Formal statement

Using Relational Transducer networks as the execution model and Confluence as the consistency criterion, Ameloot et al. prove: a query Q has a coordination-free distributed evaluation plan iff Q is monotone.

In this vault

Keeping CALM - When Distributed Consistency is Easy — the definitive survey
CAP Theorem
Confluence
Monotonic Logic
Coordination Avoidance
Relational Transducer
Bloom Language
Dedalus
CRDTs
Non-monotonic Reasoning

Tombstones

Design pattern for representing deletions monotonically: instead of removing a record, mark it with a tombstone that subsequent operations recognise as “deleted”. The effective data becomes “live records minus tombstoned records”, and the underlying state only ever grows. This converts a non-monotonic delete into a monotonic insert, enabling coordination-free operation in line with the CALM Theorem.

Standard in log-structured storage (LSM trees), Cassandra, CRDTs like OR-Set, and distributed garbage-collection schemes.

In this vault

Immutable Data Structures

Data whose values never change after construction — state updates create new values rather than mutating existing ones. Immutability is a monotonic discipline: the set of values in existence only grows. It is one of the practical design patterns the CALM Theorem motivates for coordination-free distributed systems, alongside Tombstones and CRDTs.

Functional-programming heritage (persistent trees, zippers, deforestation) carries directly into the distributed setting: immutable logs, append-only storage, event-sourced architectures, deforested pipelines.