"CAP theorem: pick two of Consistency, Availability, Partition tolerance" is the most repeated, and most subtly wrong, sentence in distributed systems. It's wrong because Partition tolerance isn't actually a choice — networks partition whether you want them to or not, so "picking" P isn't optional, and the real theorem is about what you do during a partition, not a permanent three-way trade you set once at design time. This article gives CAP its full, formal treatment: precise definitions of C, A, and P as the original paper and its formal proof use them, why "pick two" as commonly taught is misleading, a proper proof sketch, and the specific misconceptions (CA systems don't exist in any meaningful sense; "eventual consistency" is not what CAP's C means) that trip up almost everyone on a first pass.
Where CAP actually comes from
Eric Brewer stated it as a conjecture in a 2000 keynote at PODC (the ACM Symposium on Principles of Distributed Computing), based on his experience building large-scale web infrastructure at Inktomi. It remained an informally-stated industry rule of thumb — repeated, debated, occasionally misquoted — until Seth Gilbert and Nancy Lynch formally proved it in 2002, giving it a precise mathematical statement and turning "Brewer's conjecture" into an actual theorem with a proof. That 2002 paper — "Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services" — is the primary source, and it's worth naming up front because most popular explanations of CAP drift quite far from what that paper actually proves.
The three properties, defined precisely
Precision matters enormously here, because casual definitions are exactly where the popular explanations go wrong.
Consistency (C)
In the CAP formulation, Consistency means linearizability: every read receives either the most recent write's value, or an error. Not "eventually the same value everywhere" — immediately the most recent value, as if there were only a single copy of the data, with operations appearing to take effect atomically at some point between their invocation and response. This is a much stronger guarantee than the "consistency" in, say, ACID's C (which is about database integrity constraints, a completely different and unrelated meaning of the same English word — a genuinely common point of confusion since both are abbreviated "C").
Availability (A)
Every request received by a non-failing node must result in a response — not an error, not a timeout, an actual response, and within a reasonable amount of time (the original paper doesn't hard-bound the time, but the practical reading always assumes "before the client gives up"). Critically: availability in CAP is about the system as a whole always answering, not about uptime percentage or "the system is up 99.9% of the time." A system that responds instantly with an error is, by CAP's specific definition, not available — an error is not "a response" in the sense CAP means.
Partition tolerance (P)
The system continues to operate despite an arbitrary number of messages being dropped (or arbitrarily delayed) by the network between nodes. This is the property most explanations gloss over fastest, and it's the one where the "pick two" framing falls apart.
The proof, sketched properly
The formal proof (Gilbert & Lynch, 2002) is an asynchronous-network impossibility result, and the sketch is genuinely simple once you see it — this is a rare case where the popular intuition and the formal proof aren't far apart:
The proof sketch, step by step
Take two nodes, G1 and G2, each holding a replica of a value x, initially both x=0, connected by a network that can be partitioned (i.e., messages between them can be delayed arbitrarily or dropped — this is the async-network assumption, and it's what makes the proof apply to real networks, which cannot bound message delay). Partition the network so no message from G1 reaches G2 or vice versa. A client writes x=1 to G1. G1, to remain available, must respond to the write without waiting for G2 (it can't reach G2 — the partition is active). So G1 acknowledges x=1. Now a different client reads x from G2. G2, to remain available, must respond — it cannot wait indefinitely for the partition to heal. But G2 has not received the write (the partition blocked it), so G2's only available responses are either the stale x=0 (violating Consistency — this isn't the most recent write) or an error/no-response (violating Availability by CAP's own definition). There is no third option — under partition, you must pick one violation or the other. QED, informally.
Notice what the proof actually requires: an asynchronous network (no bound on message delay — which is a very close model of the real internet, as established in article 1.1's "Lie #1"), and it only kicks in while a partition is actually happening. This is the detail almost every "pick two" summary drops, and it's the single most important correction this article makes.
Fig 1 — The proof compressed to one diagram: during an active partition, G2 must choose between a wrong answer and no answer.
The misconceptions "pick two" causes
Misconception 1 — "CA systems exist"
You'll see systems (some single-node relational databases, in particular) labeled "CA" in older CAP diagrams. This is only coherent if you read it as "consistent and available, as long as there's never a partition" — which for a genuinely single-node system with no network between replicas at all is trivially true (there's nothing to partition), but for anything with more than one node, claiming "CA" is really claiming "we haven't experienced a partition yet," not "we've solved an impossible problem." Gilbert and Lynch's own later writing is explicit that CA, in the presence of a real partition, is not an achievable point — it's not on the table once you accept P is not optional.
Misconception 2 — "CP means always consistent, AP means always available"
Wrong on both counts, and this is the one that costs the most in real design conversations. A CP system doesn't sacrifice availability always — it sacrifices it only during an active partition. The other 99.9%+ of the time (no partition happening), a CP system is both consistent and available — CAP says nothing at all about that normal-operation case, because the theorem is specifically about the moment of partition. Symmetrically, an AP system doesn't sacrifice consistency permanently — during a partition it serves possibly-stale reads, but once the partition heals, it reconciles and converges back to a consistent state (this is exactly what "eventual consistency" means, and it's a real, bounded-in-practice trade-off, not "give up on correctness forever").
Misconception 3 — "Consensus algorithms like Raft are 'CP'"
Commonly stated, and directionally reasonable, but worth being precise about what it actually means: a Raft-based system remains available to the majority partition during a network split — it doesn't go fully unavailable, it goes unavailable only on the minority side, while the majority side keeps serving both reads and writes normally, fully consistently. Calling the whole system "CP" is shorthand for "on the side that can't form a majority, it refuses to serve rather than risk incorrect answers" — which is a more precise and more useful statement than the label alone conveys.
Misconception 4 — "CAP's consistency is the same as eventual/strong consistency terminology used elsewhere"
CAP's C is specifically linearizability. "Eventual consistency" (used to describe AP systems) is a genuinely different, weaker consistency model — not a lesser version of CAP's C measured on the same scale, but a different point in a much larger space of consistency models (this space — including causal consistency, sequential consistency, read-your-writes, and others — is its own rich subfield that CAP's binary C/no-C framing necessarily flattens).
| Common phrase | What it's usually taken to mean | What's actually true |
|---|---|---|
| "Pick two of C, A, P" | A permanent, symmetric three-way design choice | P isn't optional over a real network; the real choice is C vs A only during an active partition |
| "CA system" | A system that has consistency and availability with partition tolerance simply omitted | Only coherent for genuinely single-node systems; for multi-node systems it means "hasn't hit a partition yet," not an achieved guarantee |
| "CP means never available" | The system is unavailable a meaningful fraction of the time | Unavailable only during partitions (typically rare, and usually only on the minority side of the split) |
| "AP means never consistent" | Data integrity is permanently compromised | Temporarily inconsistent during partitions, converges afterward — a bounded, engineered trade-off |
Applying CAP in an actual design conversation
The genuinely useful question CAP hands you isn't "which letter do I want" — it's: when a partition happens, which side does my specific system need to fail toward? A few concrete, opposite examples:
- Bank account balance / payment ledger — favors C. A stale balance that lets someone double-spend during a partition is a much worse outcome than the system briefly refusing to process a transaction. This is why financial systems lean heavily on consensus-backed (CP-leaning) storage for the ledger itself, even at some availability cost.
- Shopping cart — the canonical AP example, and Amazon's original Dynamo paper is explicit about this choice: refusing to let a customer add an item to their cart because of a network blip is worse than briefly showing a slightly stale cart that gets reconciled a moment later. Availability wins here.
- DNS — massively AP, by necessity and by design; a stale DNS record resolving to an old IP for a few minutes during propagation is a completely acceptable, well-understood trade-off against DNS ever failing to resolve at all.
- Distributed lock service (etcd, ZooKeeper — Phase 8) — must be C, unconditionally. A lock service that gives out the same "exclusive" lock to two different clients during a partition isn't a degraded lock service — it's a broken one, because the entire point of a lock is the guarantee it never lies about exclusivity.
FAQ
If partition tolerance isn't optional, why does the acronym include it as if it were a choice?
Historically the "pick two" phrasing predates the formal 2002 proof and was Brewer's informal way of communicating the tension at the time; it stuck in popular teaching even after the formal treatment made clear P isn't a symmetric third option. This is a well-documented critique — including from Brewer himself in a 2012 retrospective ("CAP Twelve Years Later") where he explicitly walks back the "pick two" framing as an oversimplification of what he actually meant.
Does CAP apply to a single-node database?
Not meaningfully — CAP is a statement about systems with more than one node connected by a network that can partition. A single node has nothing to partition from, so the theorem's precondition doesn't apply, which is exactly why labeling a single-node database "CA" is technically true but not saying anything CAP-specific.
Is a system that's "CP" during partitions always slower during normal operation than an "AP" one?
Not necessarily from CAP alone — CAP says nothing about latency during normal (non-partitioned) operation. In practice, though, CP systems often do pay a latency cost even when healthy, because achieving strict consistency typically requires coordination (waiting for quorum acknowledgment) on every write. This latency-during-normal-operation question is specifically what PACELC (article 1.4) adds on top of CAP.
Can a system change its CAP behavior at runtime?
Yes, and many real systems do exactly this via configuration — for example, a database might let you choose per-query or per-table whether to require a quorum read (favoring C) or accept a local replica read (favoring A, with possible staleness). This reinforces the point that CAP is better understood as a spectrum of choices you make deliberately per use case, not a single label stamped on an entire system.
How does CAP relate to the FLP impossibility theorem covered later in this series?
They're related but distinct results, and it's worth flagging the connection now even though FLP gets its own full treatment in article 2.5. CAP says you can't have C and A simultaneously during a partition. FLP says something stronger and different: in a fully asynchronous network (no partition even required — just no bound on message delay), no deterministic algorithm can guarantee consensus in bounded time if even one node might fail. FLP is part of why practical consensus algorithms use timeouts and randomization rather than a purely deterministic guaranteed-termination approach — you'll see this motivation explicitly when Paxos and Raft are introduced in Phase 5.
Takeaways
- CAP was Brewer's 2000 conjecture, formally proved by Gilbert & Lynch in 2002 — the popular "pick two" phrasing predates and oversimplifies the actual proof.
- Consistency in CAP means linearizability — the most recent write, always, not "eventually the same everywhere." Availability means every non-failing node returns a real response, not an error. Partition tolerance means surviving arbitrary message loss/delay.
- Partition tolerance is not optional over any real (async) network — the real theorem says you can't have both C and A during an active partition, not that you permanently pick two of three at design time.
- The proof is a two-node thought experiment: during a partition, the node that didn't receive a write must either answer with stale data (breaking C) or refuse to answer (breaking A) — there's no third option.
- "CA systems" are only coherent for single-node deployments; "CP means always unavailable" and "AP means always inconsistent" are both false — both trade-offs apply only during partitions, which are (ideally) rare.
- The genuinely useful design question CAP hands you: for this specific piece of data, which is worse — a wrong answer or no answer, when a partition hits? Different data in the same system can reasonably answer this differently.
- CAP is a real but incomplete framework — it says nothing about the far more common case of a network that's merely slow, not partitioned. That's exactly PACELC's subject, next.
References & further reading
- Gilbert & Lynch — Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services (2002) — the primary source; the formal proof this article sketches.
- Brewer — Towards Robust Distributed Systems (PODC 2000 keynote) — the original informal conjecture.
- Brewer — CAP Twelve Years Later: How the "Rules" Have Changed — Brewer's own retrospective, explicitly correcting the "pick two" oversimplification.
- Kleppmann — Please Stop Calling Databases CP or AP — a sharp, widely-cited critique of coarse CAP labeling in practice.
- cvam.sight — Consensus 1.2: The Replication Problem — the split-brain mechanics this article's proof sketch formalizes.