Algorithm 55 / 60 Phase 10 · Distributed Systems Style: notebook-3d

CAP Theorem

The law that decides what your database is allowed to promise when the network breaks.

CAP Theorem notebook-style infographic: consistency, availability, partition tolerance triangle with CP and AP system examples

Core Concept

In a distributed data store, when the network between nodes drops messages — a partition — you cannot simultaneously keep every read consistent (all nodes agree on the latest write) and keep the system available (every request gets a non-error answer). You must sacrifice one.

The name misleads people into "pick two of three." That is wrong. Partition tolerance is not a design choice — packets get dropped, cables get cut, switches reboot. P is a fact of the world. So the real theorem is much narrower and much more useful: during a partition, choose consistency or availability. When the network is healthy, you can have both.

The one-line version Partitions will happen. When one does: refuse to answer (CP) or answer with possibly stale data (AP). There is no third door.

Key Components

C

Consistency

Every read returns the most recent write, or an error. This is linearizability, not the "C" in ACID — it means the cluster behaves like one single copy of the data.

A

Availability

Every request to a non-failed node returns a non-error response — in bounded time. Note it says a response, not a correct one.

P

Partition Tolerance

The system keeps operating when arbitrary messages between nodes are lost. Not optional in any real multi-machine deployment.

Beyond CAP

PACELC

If Partition → choose A or C; Else (normal operation) → choose Latency or Consistency. This captures the daily trade-off CAP ignores.

How It Works

  1. Two nodes, one datasetNodes N1 and N2 both hold key x = 1. A client can write to either. So far, so good.
  2. The link failsThe network between N1 and N2 drops. Each node is alive and reachable by clients, but they can no longer talk to each other.
  3. A write arrives at N1Client A writes x = 2 to N1. N1 cannot replicate it to N2. Now the two nodes disagree.
  4. A read arrives at N2 — the fork in the roadN2 must either return the stale x = 1 (chose availability, broke consistency) or refuse to answer until it can confirm with N1 (chose consistency, broke availability).
  5. Recovery and reconciliationWhen the link heals, CP systems already have one truth. AP systems must merge divergence — last-write-wins, vector clocks, or CRDTs. That merge cost is the price of having stayed up.
ChoiceBehaviour under partitionReal systems
CPRejects or blocks writes on the minority side; needs quorum to proceedetcd, ZooKeeper, HBase, Spanner
APAccepts reads and writes everywhere; reconciles laterCassandra, DynamoDB, Riak, Couch
CAOnly coherent on a single node or a network that never partitionsA single-box RDBMS — not a distributed choice

Real-World Applications

Bank ledger / payments → CPDouble-spending is unacceptable. etcd or Spanner will refuse writes on the isolated side rather than let two truths exist. Downtime beats a wrong balance.
Shopping cart / product views → APDynamoDB and Cassandra keep taking "add to cart" during a partition. A briefly stale cart is a far cheaper failure than a store that won't sell.
Service discovery & leader election → CPZooKeeper and etcd back Kubernetes control planes: two nodes both believing they are leader is worse than a short pause with no leader.
DNS and CDN edges → APAnswers are cached and eventually consistent by design. Global availability matters more than every resolver seeing a record change in the same instant.
Beginner mistake: treating CAP as a per-database label. It is a per-operation decision. Cassandra with QUORUM reads and writes behaves CP-ish for that query; MongoDB with readConcern: local behaves AP-ish. The tuning knob is where the real engineering lives.

Checkpoint — answer before you move on

  1. Why is "pick any two of C, A, P" a misreading of the theorem? Hint: which of the three is a property you choose, and which is a property of the network?
  2. A client writes x=2 to one side of a partition, then reads x from the other side. Describe exactly what a CP system does and what an AP system does — and what each one costs you. Hint: one answer is an error or a hang; the other is a stale value plus a merge problem later.
  3. What does PACELC add that CAP leaves out, and why does that addition matter more on a normal day than CAP does? Hint: how often is your network actually partitioned versus how often you pay for a quorum round-trip?