The CAP theorem
A Socratic walk-through of the CAP theorem — reasoned out one step at a time, not lectured.
The question we started with
THE QUESTION #Why must a system spanning several machines give something up the moment the network between them breaks?
The theorem is usually recited as "pick two of three: consistency, availability, partition tolerance". That sounds like a menu, and the natural response is to ask which two your system chose — as though partition tolerance were something you could decline.
But you cannot decline it. Networks between machines fail: cables, switches, routing changes, a data centre link. You do not choose whether that happens, only what your system does when it has. So "pick two" misleads, and the useful question is narrower: given that the machines can no longer talk, what forces a loss, and which loss is it?
Reasoning it through
REASONING #Set up the smallest case. Two machines, each holding a copy of one value, both currently reading blue. The network between them fails completely; each is still running and reachable by clients. A client asks machine A to write green; a client asks machine B to read.
What can B do? It cannot know about the write — there is no path from A — so it has exactly two options.
It can answer blue. That is a response, so the system stayed available, but it is stale and A and B disagree. Consistency — every read seeing the most recent write — is gone.
Or it can refuse, erroring or hanging. It has preserved the guarantee that no client is told something out of date, but it has stopped serving. Availability is gone.
Is there a third option? This is where people reach for a clever protocol, so be precise. Any correct answer B could give depends on information existing only on A, and there is no channel. Any scheme — a quorum, a lease, a timestamp, a lock — either requires communication (unavailable) or amounts to guessing (a correctness violation, not a protocol). The impossibility is informational, not a limit of current engineering, which is why it is a theorem rather than a rule of thumb. Eric Brewer conjectured it in 2000; Seth Gilbert and Nancy Lynch proved it in 2002, for strict definitions: consistency means linearizability, availability means every request to a non-failing node gets a non-error response, and partition means arbitrary message loss.
Those definitions matter more than the acronym. "Availability" here means every node answers every request. A system that fails over to a majority partition and serves there is not available in the theorem's sense, yet is very much available to most users. Much of the confusion around CAP comes from arguing about real systems using definitions strict enough to make the proof work.
Now notice what happens when there is no partition, which the acronym hides entirely. If the network is fine, must you choose? No — you can have both, and many systems do. But a quieter trade remains: guaranteeing consistency means coordinating with other nodes, and coordination costs latency, every time. Daniel Abadi formalised this as PACELC in 2012: if Partitioned, choose between A and C; Else, between Latency and Consistency. That second clause describes the trade your system makes almost all of the time, and CAP says nothing about it.
What does a system actually do at the moment of a partition? Usually something more careful than "choose C" or "choose A". A quorum system lets the majority side serve with full guarantees while the minority refuses — consistent everywhere, available to most. An offline-tolerant system accepts writes on both sides, records enough version information to detect the conflict, and reconciles on heal. Neither is "picking two"; both decide which requests get which treatment, per operation rather than once for the database.
The analogy
THE ANALOGY #Think of two branch offices keeping the same ledger, connected by a phone line. The line goes dead. A customer walks into the second branch and asks the balance. The clerk can quote yesterday's figure — fast, helpful, possibly wrong if head office has just processed something. Or say "I cannot confirm that until the line is back" — never wrong, but unhelpful, and the customer leaves. There is no third answer, because the information the clerk needs is on the other end of a dead line.
a clerk can usually tell the line is dead, whereas a machine cannot distinguish a partitioned peer from a slow or crashed one — all three look identical, so the system must act on a timeout, and a timeout is a guess dressed as a fact.
Clarifying the model
THE MODEL #Three refinements, and one correction.
First, the correction: "pick two" is the wrong reading, and its harm is real. It suggests CA is an option, and systems have been described as CA when what was meant was "we assume partitions do not happen". A single-machine database is genuinely CA — nothing to partition. Anything spanning machines is choosing between CP and AP whether anyone wrote it down or not, and if nobody did, a default timeout somewhere made the choice.
Second, the choice is not made once per system. The same partition should plausibly stop a payment being taken twice while letting a page view be counted approximately. The useful question is per-operation: what does a stale answer cost here, against no answer at all? That turns an architecture debate into small, answerable product questions.
Third, "eventual consistency" is not the absence of a choice; it is the AP branch plus a commitment to reconcile. Reconciliation is real work: last-write-wins silently discards data and needs clocks it does not have; version vectors detect conflicts but hand them back; conflict-free replicated data types resolve automatically, but only for operations that genuinely commute. Choosing AP is choosing to write that merge logic.
A last note: the theorem's own authors say the framing has outlived its usefulness. Brewer's 2012 retrospective, "CAP Twelve Years Later", argues the real engineering lies in detecting a partition, limiting what is permitted during one, and recovering afterwards — not in picking a letter.
A picture of it
THE PICTURE #How to readStart at the entry point in the healthy state, where both properties hold and only the quiet latency trade applies — the note on the right, and the state a system is in almost always. The edge into Suspected is a timeout, not an observation, which is the note that matters most: nothing here can tell a partition from a slow peer. The two edges out of Suspected are the actual CAP choice, and their labels are the question a designer answers per operation rather than per system. Follow the consistent branch and healing is trivial, since no divergence occurred; follow the available branch and healing needs a real merge, the deferred cost of having stayed up.
What became clearer
WHAT CLEARED #CAP is not a menu of three but a forced choice between two, triggered by a condition you do not control. When two machines cannot exchange messages, a node asked about data it cannot verify may answer possibly-stale or answer nothing, and no protocol escapes that, because the required information is not present. The proof's definitions are narrower than everyday usage, which is why so many real systems fit neither label cleanly. And the trade governing most of a system's life is not in the acronym at all: the latency spent on coordination while the network is perfectly healthy.
Where to go next
ONWARD #- What linearizability actually requires, and how it differs from the serializability a transactional database offers.
- How quorum systems keep strict guarantees on the majority side of a partition, and what happens when there is no majority.
Key terms
TERMS #| Term | What it means |
|---|---|
| Partition | a network failure in which some nodes cannot exchange messages with others while all remain running. |
| Linearizability | the strict consistency the theorem uses: every operation appears to take effect at a single instant between its start and its return. |
| Availability (in CAP) | the strict form: every request to a non-failing node receives a non-error response. |
| PACELC | Daniel Abadi's 2012 extension: if partitioned, trade availability against consistency; else, trade latency against consistency. |
| Conflict-free replicated data type | a data structure whose concurrent updates commute, so replicas converge without coordination. |
Every term the collection defines is gathered in the glossary.