Skip to content

CAP / PACELC — Notes#

CAP precise statement (Gilbert & Lynch, 2002)#

For any read/write register replicated across nodes connected by an asynchronous network, you cannot simultaneously guarantee: - Linearizability (C) - Total availability (every non-failing node responds non-error) (A) - Tolerate network partitions (P)

In real networks P is unavoidable → pick CP or AP.

PACELC (Abadi 2010)#

If a Partition, choose A or C. Else, choose L (latency) or C.

This captures the normal-mode trade-off CAP misses: synchronous replication ≈ low-latency loss.

Consistency model lattice (strong → weak)#

  1. Linearizable
  2. Sequential
  3. Causal
  4. Read-your-writes / Monotonic reads
  5. Eventual

Common misconceptions#

  • "We're CA because no partitions in our DC" — partitions are still possible (rack switch, GC pause).
  • "Eventual = inconsistent forever" — usually converges in ms; bounded staleness is precise term.
  • Spanner is "CP" but with 99.999% availability — proving P doesn't always mean unavailable.

Refs#

  • Gilbert, Lynch (2002): "Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services."
  • Abadi (2010): "Consistency Tradeoffs in Modern Distributed Database System Design."
  • Spanner OSDI '12 paper. Jepsen analyses (https://jepsen.io).