CAP Theorem

A distributed data store can provide at most two of the following three guarantees in the presence of a network partition: Consistency, Availability, Partition tolerance.

Conjectured by Eric Brewer (2000) in his PODC keynote; proved by Seth Gilbert and Nancy Lynch at MIT (2002).

The Three Properties

• Consistency (C). Every read receives the most recent write — the system behaves as if there is a single copy of the data. (Specifically, linearisability.)
• Availability (A). Every request to a non-failing node receives a response, without guarantee that it contains the most recent write.
• Partition tolerance (P). The system continues to operate despite arbitrary loss of messages between nodes.

The theorem states that when a network partition occurs, you must sacrifice either consistency or availability. Not both. You must choose.

Why You Can’t Have All Three

Imagine two nodes, A and B, each holding a copy of the data. A client writes to A. The network between A and B fails (partition). Now:

• If the system responds to a read at B → the client gets stale data (no C).
• If the system refuses to respond at B → B is unavailable (no A).
• The only third option — not tolerate partitions — means the system falls over entirely when the network is slow or flaky (no P).

In any real distributed system, partitions will happen (Murphy’s Law at network scale). So P is not negotiable; the actual trade-off is between C and A during partitions.

The Practical Taxonomy

Class	Example Systems	Behaviour on Partition
CP (consistency + partition tolerance)	Spanner, etcd, MongoDB (with majority writes), ZooKeeper	Refuses writes or reads on the minority side; possibly unavailable
AP (availability + partition tolerance)	DynamoDB (default), Cassandra (default), Riak, CouchDB	Always answers, possibly with stale or conflicting data; reconciliation later
CA (consistency + availability, no P)	Single-node databases; synchronous two-phase commit on a single rack	Only works as long as the network is perfectly reliable — which in practice, isn’t

The “CA” category is the most misunderstood. Pure CA systems don’t exist at scale because partition tolerance isn’t really optional — the question is just how you handle partitions when they occur.

The PACELC Refinement

Daniel Abadi’s PACELC extension (2012) sharpens CAP:

If there is a Partition (P), how does the system trade off Availability (A) and Consistency (C); ELse (E), when operating normally, how does it trade off Latency (L) and Consistency (C)?

The insight: the C/A trade-off is only interesting during partitions, but there is a parallel L/C trade-off all the time. Even without a partition, achieving stronger consistency requires more coordination — which adds latency. PACELC captures both trade-offs explicitly. Spanner is PC/EC; DynamoDB is PA/EL; Cassandra is PA/EL.

In This Wiki

• A worked-out theorem, not a folk law. Unlike most of source—laws-of-software-engineering, CAP is a formal result with a proof. It’s the closest thing in the collection to a physical law.
• Instance of Tesler’s Law / Conservation of Complexity. The CAP trade-off cannot be engineered away; it can only be shifted. Some choice of which property to sacrifice must be made somewhere in the system.
• Relates to fallacies-of-distributed-computing. The eight fallacies (“the network is reliable,” “latency is zero,” etc.) are what designers assume when they underestimate the frequency of partitions. CAP forces the assumption out into the open.
• Relates to Hyrum’s Law. Once users rely on the consistency model you ship (C or AP), switching is a breaking change. You cannot migrate a Cassandra-backed application to Spanner without application-level changes; the consistency model was load-bearing.
• Mirrors political-economy trade-offs in extractive-institutions/inclusive-institutions. Analogy (not a theorem): centralised authority (C) and broad participation (A) are tensioned in any partitioned society.
• Connects to nuclear-deterrence (loose analogy). Deterrence requires consistency (both sides must have the same read of the threshold) and availability (command systems must work even after a first strike). Partitioned communications force the hard trade-off — unclear thresholds, or unreachable launch authority.

Common Misunderstandings

1. CAP is not “pick two all the time.” It’s “pick two during a partition.” In the normal case, most systems provide all three — until the network breaks.
2. “Eventually consistent” is a relaxation of C, not an escape from CAP. AP systems are still making the trade-off; they’ve just chosen to weaken consistency to a weaker model (eventual consistency, read-your-writes, etc.).
3. Modern systems often provide tunable consistency. Cassandra, DynamoDB, and Cosmos DB let you pick per-operation: strong consistency when you need it (slower, may be unavailable), eventual consistency when you don’t (fast, always available). This doesn’t escape CAP; it surfaces the trade-off to the application developer.

Sources

• source—laws-of-software-engineering — in the Architecture cluster.
• Eric Brewer, PODC 2000 keynote — original conjecture.
• Seth Gilbert & Nancy Lynch, “Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services” (2002) — formal proof.
• Daniel Abadi, “Consistency Tradeoffs in Modern Distributed Database System Design” (2012) — PACELC extension.