CAP, consistency and consensus
What CAP actually says, a quorum simulation where R + W > N removes stale reads and refuses writes in a partition, consistency models, PACELC, and Raft in one page.
CAP is the most quoted theorem in system design and one of the most misquoted. "Pick two of consistency, availability and partition tolerance" is the version most people learn, and it is wrong in a way that leads to bad designs: you do not get to pick partition tolerance. Networks partition. The theorem is about what your system does when that happens.
What CAP actually says
Eric Brewer stated the conjecture in 2000; Seth Gilbert and Nancy Lynch proved a formal version in 2002. In their terms:
- Consistency means linearizability: every read sees the most recent completed write, as if there were one copy of the data.
- Availability means every request to a non-failed node gets a non-error response.
- Partition means the network drops messages between some nodes.
The theorem: during a partition, a system cannot guarantee both. A node cut off from the others can answer — and risk answering with stale data — or refuse, and be unavailable. That is the whole choice, and it only exists while the partition lasts.
Two consequences that the "pick two" version hides:
- When there is no partition, you can have both. CAP says nothing about normal operation.
- Most systems are not purely one or the other. They make different choices for different operations, and the choice is often configurable per request.
The quorum, measured
The mechanism behind most of these choices is the quorum. With N replicas of a value, a write is acknowledged once W replicas have it, and a read asks R replicas and takes the newest version it sees. The remaining replicas catch up later — replication lag.
A simulation with three replicas, a write and a read alternating 100,000 times, and the unacknowledged replicas receiving each write between 1 and 20 ticks later. Seeded, so it repeats exactly:
W=1 R=1 all replicas up stale reads 63.1% failed writes 0.0% failed reads 0.0%
W=2 R=1 all replicas up stale reads 31.4% failed writes 0.0% failed reads 0.0%
W=1 R=2 all replicas up stale reads 30.2% failed writes 0.0% failed reads 0.0%
W=2 R=2 all replicas up stale reads 0.0% failed writes 0.0% failed reads 0.0%
W=3 R=1 all replicas up stale reads 0.0% failed writes 0.0% failed reads 0.0%The rule is visible in the table: when R + W > N, every read overlaps at least one replica that has the latest write, and the stale-read rate went to zero. With W=2 and R=2 out of 3, any two replicas you read include at least one of the two that were written. Below that line, stale reads were routine — 63% with W=1, R=1, because the write happened at a rate the lag could not keep up with.
Now make replicas unreachable, as a partition would, from the point of view of a client that can reach only the rest:
W=3 R=1 1 replica(s) unreachable stale reads 0.0% failed writes 100.0% failed reads 0.0%
W=1 R=1 2 replica(s) unreachable stale reads 0.0% failed writes 0.0% failed reads 0.0%
W=2 R=2 2 replica(s) unreachable stale reads 0.0% failed writes 100.0% failed reads 100.0%That is CAP in three lines. W=3 refuses every write the moment one replica is gone. W=2, R=2 refuses everything when only one replica can be reached, because no quorum exists. W=1, R=1 carries on — and the two replicas on the other side of the partition may be accepting different writes from other clients, which this client cannot see and nobody can reconcile until the partition heals.
The model is deliberately small — fixed membership, no clocks, a single value — and real systems add complications that weaken the guarantee: sloppy quorums that accept writes on substitute nodes during failures, and last-write-wins conflict resolution based on timestamps that drift. The overlap rule is the core; those details are why a system that says "quorum" should still be read carefully.
Consistency models, strongest to weakest
"Consistent" is not one thing. The useful models, in decreasing strength:
| model | promise | what it costs |
|---|---|---|
| Linearizable | behaves like one copy; a completed write is visible to every later read | coordination on every operation; unavailable in a minority partition |
| Sequential | all clients see operations in the same order, not necessarily real-time order | still coordination |
| Causal | operations that depend on each other are seen in order; unrelated ones may not be | tracking dependencies; available in partitions |
| Read-your-writes | a client sees its own writes | session stickiness or leader reads for that client |
| Monotonic reads | a client never sees data go back in time | pinning a client to a replica |
| Eventual | if writes stop, replicas converge | nothing — and it promises nothing about what you read meanwhile |
Most applications need linearizability for a few things — balances, stock, uniqueness of a username — and much weaker models for the rest. The design skill is deciding per operation rather than per database.
PACELC: the choice you make every day
CAP describes behaviour during a partition, which is rare. Daniel Abadi's PACELC extension adds the choice that exists all the time:
If there is a Partition, choose Availability or Consistency; Else, choose Latency or Consistency.
Even with a healthy network, waiting for W=2 acknowledgements is slower than waiting for one. Every synchronous replica, every quorum read, adds latency on every request. That trade-off — not partitions — is what most teams actually tune.
Consensus, and why Raft exists
Quorums handle reading and writing values. Some decisions need more: which node is the leader, whether a transaction committed, what the configuration of the cluster is. Those need every node to agree on one answer, even when messages are lost and nodes crash — and a single failure detector cannot tell a dead node from a slow one.
That is the consensus problem, and it is solved by protocols that rely on majority quorums: Paxos, which is notoriously hard to understand and implement, and Raft, designed by Diego Ongaro and John Ousterhout explicitly to be understandable. Raft in one page:
- Leader election. Nodes are followers. If a follower hears nothing from a leader for a randomised timeout, it becomes a candidate, increments the term, and asks for votes. A candidate with votes from a majority becomes leader for that term.
- Log replication. The leader appends each command to its log and sends it to followers. An entry is committed once a majority has stored it; only then is it applied and acknowledged.
- Safety. A node votes only for a candidate whose log is at least as up to date as its own, so a new leader always has every committed entry. A leader from an older term that reappears sees a higher term and steps down.
Majorities are what make it safe: two majorities of the same cluster always share at least one node, so two leaders cannot both be elected in the same term. That is also why consensus clusters have odd sizes — three nodes survive one failure, five survive two, and four survive only one, same as three.
You will rarely implement Raft. You will use it constantly: etcd, which stores Kubernetes' cluster state, uses Raft; so does Kafka's KRaft mode for its metadata, and Consul. Knowing what it guarantees tells you what those systems do in a partition — the minority side stops accepting writes.