Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services (The CAP Theorem)

In 2000, Eric Brewer gave a keynote at PODC arguing that a distributed data store cannot simultaneously guarantee three things engineers wanted all at once: strong consistency, full availability, and tolerance of network partitions. It was stated as a conjecture, backed by experience running Inktomi's search infrastructure, not a proof. Two years later, Seth Gilbert and Nancy Lynch at MIT turned it into an actual theorem, with a formal model and a short, tight proof. That paper is what most engineers mean today when they say "the CAP theorem."

The result is small, almost embarrassingly so for something this widely cited: two nodes, one write, one read, one dropped message. But it explains a decision every distributed database makes, often silently, and it is the reason Dynamo and Raft, both covered elsewhere on this site, land on opposite sides of the same tradeoff.

Three words that need precise definitions

Gilbert and Lynch's contribution was not the idea, Brewer already had that, it was pinning down exactly what each of the three words means, precisely enough to prove something about them.

• Consistency: every read receives the result of the most recent write, or an error. This is the strong, single-copy notion the paper calls atomic consistency (equivalent to what later literature calls linearizability), not the C in ACID, which is a different, weaker property about database constraints.

• Availability: every request to a non-failing node must eventually receive a response, one that is not an error. A node that is up but refuses to answer is not available in this sense, even if it is technically still running.

• Partition tolerance: the system continues to operate even when the network drops an arbitrary number of messages between nodes. The paper models this as an adversary who can delete any message sent between two nodes it has split apart.

The proof, compressed to its essence

The paper's argument uses the smallest possible system: two nodes, $G_1$ and $G_2$, each holding a copy of some value $x$. A partition cuts every message between them. A client writes $x = v_1$ to $G_1$. Because the network is partitioned, that write cannot reach $G_2$.

Now a different client asks $G_2$ to read $x$. $G_2$ has exactly two options, and no third one exists:

• Answer with the old value $v_0$. The request gets a response, satisfying availability, but that response is wrong given the write that already happened, so consistency is broken.

• Refuse to answer until it can confirm the current value, by which point the partition may not even be resolved. Consistency stays intact, but the request that should have gotten a response did not, so availability is broken.

That is the entire proof. There is no clever protocol, no amount of engineering skill, that lets $G_2$ do both at once during the partition, because doing both requires information that the partition, by definition, is preventing from arriving. The theorem is a statement about information flow under failure, not about anyone's implementation being clumsy.

The moment a partition separates two nodes, a read on the isolated side must pick one: answer with possibly stale data (available) or refuse to answer (consistent).

"Pick any two of three" is a popular oversimplification

The theorem is usually summarized as "consistency, availability, partition tolerance: pick two." That framing has stuck for twenty years and it is misleading. Partition tolerance is not a feature you can decline for a system with more than one node communicating over an unreliable network, which describes essentially every real distributed system. You cannot forbid the network from ever dropping a packet.

What the theorem actually restricts is narrower and more useful: the choice between consistency and availability only has to be made during an actual partition. The rest of the time, when the network is healthy, a well-built system can offer both. So "CP" and "AP" describe what a system does when things go wrong, not what it offers all the time.

Real systems leaning each direction. Raft-based systems like etcd and ZooKeeper give up availability during a partition to keep every read strongly consistent. Dynamo-style systems give up strict consistency to keep answering requests.

The theorem's sequel: PACELC

A fair criticism of CAP, raised most clearly by Daniel Abadi in 2012, is that it only describes behavior during a partition, but partitions are rare. Most of the time, a system is up and fully connected, and there is still a tradeoff to make: how much latency are you willing to pay for stronger consistency on every single request, partition or not?

Abadi's PACELC formalizes this: if Partitioned, choose between Availability and Consistency (the original CAP tradeoff); Else, choose between Latency and Consistency (a tradeoff that exists even on a perfectly healthy network, because synchronous replication to stay consistent always costs round-trip time). It is a more complete map of the same underlying design space, and it is worth knowing the name because you will see databases described as "PA/EL" (Dynamo, Cassandra) or "PC/EC" (spanner-style systems that pay latency for consistency even when healthy) in vendor documentation.

Why this still shapes every system design conversation

The CAP theorem is why "it depends" is frequently the honest answer to "should this database be strongly consistent." It reframes the question from a matter of engineering effort into a matter of what happens to be true when the network breaks, which is unavoidable at scale. Once you internalize it, reading any database's documentation changes: you start looking for the sentence that admits what it does during a partition, because that sentence tells you more about the system than almost anything else in the docs.