Lesson 25 · Consistency models · Module 3
CAP, and What It Does Not Say
CAP is the most-cited and least-read result in distributed systems. It is a narrow, precise statement about one moment — the moment packets stop arriving — and almost everything said about it in design reviews concerns moments it never mentions.
The win in this lesson: you will be able to correct a misuse of CAP out loud, without hand-waving, and you will have a better daily framing to replace it with — PACELC, which covers the 99-point-something percent of the time when nothing is partitioned at all.
1. The problem: a theorem used as a slogan
"We're AP, so we can't do transactions." "We picked CA because we're in one region." "CAP says you can only have two." Each of these is wrong, and each is wrong in a different way — which is why arguing against them needs the actual statement, not a better slogan.
Brewer, who proposed the conjecture, says so himself:
"The '2 of 3' formulation was always misleading because it tended to oversimplify the tensions among properties. […] CAP prohibits only a tiny part of the design space: perfect availability and consistency in the presence of partitions, which are rare."
CAP Twelve Years Later: How the "Rules" Have Changed — Eric Brewer, IEEE Computer, February 2012
So: a tiny part of the design space, and only during something rare. Start there.
2. The theorem, stated precisely
The Cambridge distributed systems notes give the version worth memorising, because it names the trigger and enumerates the two branches:
"This trade-off is known as the CAP theorem (named after consistency, availability, and partition tolerance), which states that if there is a network partition in a system, we must choose between one of the following options: 1. We can have linearizable consistency, but in this case, some replicas will not be able to respond to requests because they cannot communicate with a quorum. Not being able to respond to requests makes those nodes effectively unavailable. 2. We can allow replicas to respond to requests even if they cannot communicate with other replicas. In this case, they continue to be available, but we cannot guarantee linearizability."
Concurrent and Distributed Systems — Martin Kleppmann, University of Cambridge, 2021–22 · §7.3
Read the conditional in the first clause: if there is a network partition. Everything CAP has to say is downstream of that if. The theorem is silent otherwise.
3. Misreading one: "pick two of three"
Partition tolerance is not a property you select. It is a description of the network you were already given. The formal paper models it as a permission granted to the adversary, not a feature of your system:
"In order to model partition tolerance, the network will be allowed to lose arbitrarily many messages sent from one node to another."
Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services — Seth Gilbert and Nancy Lynch, ACM SIGACT News 33(2), 2002 · §2.3
You do not get a vote on whether packets drop. Brewer puts the rhetorical question directly:
"Does choosing consistency and availability (CA) as the '2 of 3' make sense? As some researchers correctly point out, exactly what it means to forfeit P is unclear. Can a designer choose not to have partitions? If the choice is CA, and then there is a partition, the choice must revert to C or A."
Brewer 2012, "CAP Confusion" sidebar
"CA" is not a design. It is a bet that partitions are rarer than the other ways the system dies — and Brewer says exactly that: "choosing CA should mean that the probability of a partition is far less than that of other systemic failures, such as disasters or multiple simultaneous faults." If you claim CA and a partition happens anyway, you did not avoid the choice. You made it by accident, at 3 a.m., without a plan.
4. Misreading two: C is not ACID's C
They are different letters that happen to share a glyph. Brewer separates them explicitly:
"In ACID, the C means that a transaction preserves all the database rules, such as unique keys. In contrast, the C in CAP refers only to single-copy consistency, a strict subset of ACID consistency."
Brewer 2012, "ACID, BASE, and CAP" sidebar
Single-copy consistency is linearizability, and it has a precise definition that says nothing about your foreign keys:
"there must exist a total order on all operations such that each operation looks as if it were completed at a single instant. This is equivalent to requiring requests of the distributed shared memory to act as if they were executing on a single node, responding to operations one at a time."
Gilbert and Lynch 2002 · §2.1
Jepsen's reference guide states the real-time clause that makes it the strong one:
"Linearizability is one of the strongest single-object consistency models, and implies that every operation appears to take place atomically, in some order, consistent with the real-time ordering of those operations: e.g., if operation A completes before operation B begins, then B should logically take effect after A."
Linearizability — Jepsen consistency reference
5. Misreading three: A is not uptime
This is the misreading that survives longest, because the everyday meaning of "available" is so close to the technical one and so much weaker. The formal definition:
"For a distributed system to be continuously available, every request received by a non-failing node in the system must result in a response. […] even when severe network failures occur, every request must terminate."
Gilbert and Lynch 2002 · §2.2
Every request. Every non-failing node. Including the one node stranded alone on the wrong side of the partition, which by that definition must still answer:
"even if every other node in the network fails (i.e. the node is in its own unique component of the partition), a valid (atomic) response must be generated."
Gilbert and Lynch 2002 · §2.3
Gilbert and Lynch note in a footnote that this is stricter than Brewer's original: "Brewer originally only required almost all requests to receive a response. As allowing probabilistic availability does not change the result when arbitrary failures occur, for simplicity we are requiring 100% availability." The proof needs the absolute version. Your SLA does not have it.
Jepsen names the consequence for the strongest model in one sentence: linearizability "cannot be totally or sticky available; in the event of a network partition, some or all nodes will be unable to make progress."
6. Misreading four: it says nothing about the normal case
And here is where the theorem is quietly abandoned by the systems that cite it. Abadi's charge:
"many designers incorrectly conclude that the theorem imposes certain restrictions on a DDBS during normal system operation, and therefore implement an unnecessarily limited system. In reality, CAP only posits limitations in the face of certain types of failures, and does not constrain any system capabilities during normal operation."
Consistency Tradeoffs in Modern Distributed Database System Design — Daniel J. Abadi, IEEE Computer, February 2012
Brewer agrees, from the other direction: "because partitions are rare, there is little reason to forfeit C or A when the system is not partitioned."
7. PACELC: the framing you will actually use
"A more complete portrayal of the space of potential consistency tradeoffs for DDBSs can be achieved by rewriting CAP as PACELC (pronounced 'pass-elk'): if there is a partition (P), how does the system trade off availability and consistency (A and C); else (E), when the system is running normally in the absence of partitions, how does the system trade off latency (L) and consistency (C)?"
Abadi 2012, "PACELC"
The second half is the half you live in. Waiting for a second replica to acknowledge is not a partition — it is a Tuesday, and it costs milliseconds on every single request.
Abadi's summary of why this matters more than the theorem does:
"Ignoring the consistency/latency tradeoff of replicated systems is a major oversight, as it is present at all times during system operation, whereas CAP is only relevant in the arguably rare case of a network partition."
Abadi 2012
8. Where real systems sit
Two letters, both chosen, and a system's reputation usually comes from only one of them.
| System | P: partition choice | E: normal-case choice |
|---|---|---|
| Dynamo, Cassandra, Riak (defaults) | availability — "they give up consistency for availability" | latency — "under normal operation they give up consistency for lower latency" |
| VoltDB / H-Store, Megastore | consistency — "they refuse to give up consistency" | consistency — "and will pay the availability and latency costs to achieve it" |
| BigTable, HBase | consistency | consistency — "also PC/EC" |
| MongoDB | availability — a new master is elected, the old one rolls back | consistency — "the system guarantees reads and writes to be consistent" |
| PNUTS | consistency — the item becomes unavailable for updates | latency — "it gives up consistency for latency" |
All quoted classifications are Abadi's, §"PACELC". Two rows deserve a second look. PNUTS is PC/EL — it gets stricter under partition, which looks like nonsense until you read Abadi's caveat: "PC does not indicate that the system is fully consistent; rather it indicates that the system does not reduce consistency beyond the baseline consistency level when a network partition occurs — instead, it reduces availability."
And MongoDB is filed as PA/EC with an asterisk of the same kind: "Technically, when a partition occurs, MongoDB is not available according to the CAP definition of availability, as the minority partition is not available." Even the people drawing the taxonomy have to keep stepping around the strictness of CAP's A.
Dynamo's "always writeable" requirement was the P-half of PACELC answered in advance: under partition, take availability. But its R and W dial — the thing you actually turn in a config file — is the E-half. Raising R and W buys consistency with latency on every request, with no partition anywhere in sight. Abadi notes this exactly: they "gain more consistency at the expense of latency (although they cannot achieve full consistency as defined by Gilbert and Lynch, even if R + W > N)."
9. Residual risk: what neither framing gives you
Four things a letter on a slide will not decide for you
- Nobody agrees a partition has started. A partition is detected by a timeout, and Brewer's pragmatic reading follows: "a partition is a time bound on communication. Failing to achieve consistency within the time bound implies a partition." Set the bound tight and you enter partition mode during ordinary slowness — "systems with tighter bounds will likely enter partition mode more often and at times when the network is merely slow and not actually partitioned."
- The choice is not made once. "the choice between C and A can occur many times within the same system at very fine granularity" — per subsystem, per operation, per user. A single letter for a whole system is always a simplification.
- Choosing A hands you an invariant problem you may not be able to state. Brewer: "when designers choose A, which requires restoring invariants after a partition, they must be explicit about all the invariants, which is both challenging and prone to error." Lesson 05's resurrected cart item is one such invariant, discovered the hard way.
- The client is part of the system. "If users cannot reach the service at all, there is no choice between C and A except when part of the service runs on the client." All the letters in the world do not help a user whose Wi-Fi is off.
10. Check yourself
11. Back to your world
You will meet CAP in a design review long before you meet a partition. Three moves that turn the slogan back into a question:
- "Which letter of C do you mean?" If the answer is about foreign keys or unique constraints, they are talking about ACID and CAP is not the relevant result.
- "What does the minority side return?" An error is CP. A possibly-stale answer is AP. This one question replaces the whole taxonomy, and most teams have never checked.
- "Forget partitions — what are we trading on a normal request?" That is the Else, it is where the latency budget goes, and it is the conversation the room was probably trying to have.