PAPERS-15-002 · Paper — The CAP Theorem — Brewer's Conjecture, Proven

The paper

The CAP Theorem — Brewer’s Conjecture, Proven, by Seth Gilbert and Nancy Lynch, published in 2002 at the ACM Symposium on Principles of Distributed Computing, is a landmark because it turned an informal intuition about distributed systems into a formal, proved theorem.

Before this paper

Before this work, Eric Brewer had conjectured a three‑way trade‑off among consistency, availability, and partition tolerance, but it was only an informal claim. Teams disagreed about what consistency and availability really meant, leading to heated debates. There was no rigorous definition or proof to settle the issue, leaving system designers without a solid foundation.

The key idea

Gilbert and Lynch’s key insight was to formalize the three properties—consistency as linearizability, availability as every request receiving a response, and partition tolerance as surviving lost messages—and then prove that no distributed algorithm can guarantee all three simultaneously when a network partition occurs.

How it works

They began by giving precise mathematical definitions for each property. Next they modeled a distributed system as a set of nodes communicating over an unreliable network that can partition. They constructed a scenario where a partition separates the nodes into two groups. In that scenario, they showed that if both sides continue to answer requests (availability) they must diverge on the data, breaking consistency; if they stay perfectly consistent, at least one side must stop answering, breaking availability. This impossibility argument forms a short, rigorous proof that the three properties cannot coexist under partition.

See it — pick two under a partition

flowchart TD
  A["Network partition<br/>happens"] --> B["Answer anyway?<br/>(Availability)"]
  A --> C["Stay correct?<br/>(Consistency)"]
  B --> D["Cannot guarantee<br/>both at once"]
  C --> D

What they showed

The result was a rigorous theorem: a distributed system cannot simultaneously guarantee Consistency, Availability, and Partition tolerance. When a partition happens, you must sacrifice either always‑consistent answers or always‑available answers.

What it changed

The theorem gave architects a precise vocabulary for the consistency‑versus‑availability trade‑off, influencing the design of NoSQL and cloud databases. Systems began to label themselves as CP or AP, and the community later extended the idea with the PACELC model. This shift clarified design choices and guided the evolution of modern distributed storage. Next: Paxos.

The one-line takeaway

In a real network that can partition, you must choose between consistency and availability.

Read it / meet it

Reading the original paper reveals the elegant simplicity of the proof and why it matters today. Its legacy lives on in every database’s consistency settings and in the ongoing discussions about CAP‑style trade‑offs in cloud services.