Symptom
You have three replicas of a value. A client writes v2 and gets an
acknowledgement. Another client reads and gets v1.
Nothing crashed. No network partition healed badly. Both operations completed successfully and reported success. The write went to one replica, the read came from another, and the two never spoke.
So you add replicas, because five feels safer than three. The bug does not go away; it gets rarer, which is worse, because now it survives your test suite and shows up in production at 3 a.m. as a support ticket saying “I saved it and it didn’t save.”
The instinct at this point is to reach for consensus, or for a stronger database, or for a distributed lock. All three are heavier than the problem. The actual fix is one inequality, and once you see it you can dial your system anywhere on the consistency-availability curve by choosing two integers.
Statement
Let $N$ be the number of replicas holding a value. Let a write be acknowledged once $W$ replicas have durably accepted it, and a read be answered once $R$ replicas have responded.
If $R + W > N$, every read quorum intersects every write quorum, so every read observes at least one replica carrying the most recent acknowledged write.
Let $\mathcal{Q}_W, \mathcal{Q}_R \subseteq 2^{[N]}$ be the write and read quorum systems. The register is regular if every $Q_r \in \mathcal{Q}_R$ and $Q_w \in \mathcal{Q}_W$ satisfy $Q_r \cap Q_w \neq \emptyset$. For threshold quorums $|Q_w| = W$, $|Q_r| = R$ over $N$ replicas, this holds iff $R + W > N$. Write-write ordering additionally requires $W + W > N$, i.e. $W > N/2$.
The proof is the pigeonhole principle (T001) wearing a hat. If two sets of sizes $R$ and $W$ drawn from $N$ elements were disjoint, they would together contain $R + W$ distinct elements out of $N$ available, and $R + W > N$ makes that impossible. So they share at least one element, and that element has the write.
Note the second condition, which is routinely dropped. $R + W > N$ gives you read-your-writes. It does not by itself order concurrent writes. For that you need $W > N/2$, so that any two write quorums also intersect and cannot both succeed with conflicting values unnoticed.
Argument
The whole content is the intersection, so the interesting work is in seeing what the knob actually controls.
The trade is latency and availability, in both directions. A write must wait for $W$ acknowledgements, so the write latency is the $W$-th fastest replica. A read waits for the $R$-th fastest. Larger $W$ means slower and less available writes; larger $R$ means slower and less available reads. Since $R + W > N$ is a budget, tightening one loosens the other.
The standard configurations for $N = 3$, with the failures each survives:
| $R$ | $W$ | $R+W>3$ | Survives for reads | Survives for writes | Shape |
|---|---|---|---|---|---|
| 1 | 3 | yes | 2 failures | 0 failures | read-optimized |
| 2 | 2 | yes | 1 failure | 1 failure | balanced |
| 3 | 1 | yes | 0 failures | 2 failures | write-optimized |
| 1 | 1 | no | 2 failures | 2 failures | eventually consistent |
The last row is the one that produced the symptom. It is also a legitimate choice, and Cassandra, Riak, and DynamoDB all let you make it per-operation. The theorem does not say it is wrong; it says what you have bought and what you have given up.
Note the asymmetry in the balanced row. $R=W=2$ tolerates exactly one failure for both operations, and it is the only $N=3$ configuration that tolerates any failure at all on both sides. This is why it is nearly always the default.
Availability is not symmetric in $N$. With $W = \lceil (N+1)/2 \rceil$ the system tolerates $\lfloor (N-1)/2 \rfloor$ write failures: 1 for $N=3$, 1 for $N=4$, 2 for $N=5$, 2 for $N=6$. Adding a replica to an odd cluster buys nothing and costs a machine, which is why quorum systems are almost always odd-sized. The even cluster is strictly worse than the odd one below it on cost and equal on tolerance.
Weighted quorums. Gifford’s original formulation assigns votes rather than counting nodes, and this is more than a generalization for its own sake. Give a replica on fast local disk three votes and a replica across an ocean one, and you can build a quorum system where the common case never crosses the ocean while the correctness argument is unchanged: the intersection condition is $R + W > $ total votes. Modern versions of this appear as witness replicas and flexible Paxos, where the read and write quorums are different shapes entirely and only the intersection is required.
Sloppy quorums are a different thing wearing the same word. Dynamo-style systems, under partition, accept a write onto whichever $W$ nodes are reachable, including nodes not in the value’s preference list, with a hinted handoff to deliver it later. Those $W$ acknowledgements do not come from the replica set, so no intersection is guaranteed and the theorem simply does not apply. This is a deliberate availability choice and it is documented as such in the Dynamo paper. It is also the single most common source of “but we configured $R + W > N$ and still read stale data.”
Forbids
Reading fresh data with $R + W \le N$. No retry policy, no read repair, no timeout tuning fixes this. The read quorum and the write quorum can be disjoint, and when they are, the read is answered entirely by replicas that never saw the write.
$W = 1$ with any expectation of durability. A single acknowledging replica that dies before replicating takes the acknowledged write with it. The client was told the write succeeded. This is not a race; it is the configuration working as specified.
Ordering concurrent writes with $W \le N/2$. Two writers can each collect a disjoint quorum and both succeed with conflicting values. The system now has two “latest” versions and must resolve them by some other means: last-write-wins (which loses data), vector clocks (T059), or CRDTs (T067). Quorum intersection alone will not do it.
Turning an eventually consistent store into a linearizable one by arithmetic alone. $R + W > N$ gives regular register semantics, not linearizability. Without a read-repair-then-return step, two concurrent reads can observe the new value and then the old one.
Does not forbid
It does not require a consensus protocol. This is the useful part. Quorum intersection is a static property of set sizes, established by counting, with no leader election, no rounds, and no view changes. Dynamo, Cassandra, Riak, and Voldemort all achieve read-your-writes with quorums and no consensus anywhere in the data path, which is why their write latency is a single network round trip rather than the two or more that Paxos (T064) needs.
It does not mean quorum systems avoid FLP. They do not solve consensus, so FLP (T062) never applies to them. They provide a weaker guarantee cheaply, which is a different and often better bargain.
It does not require $R$ and $W$ to be fixed for the system. Cassandra and
DynamoDB set consistency per operation. A session token write goes at
QUORUM/QUORUM; an analytics scan of the same table goes at ONE. The same
data can be read at different points on the curve by different callers, and
this is the normal way these systems are operated rather than an abuse of them.
It does not forbid stale reads under $R + W > N$ when the write is still in flight. An unacknowledged write may be visible to some readers and not others. The guarantee attaches to acknowledged writes only, and the phrase is doing real work.
It does not mean more replicas are more consistent. Increasing $N$ while holding $R$ and $W$ fixed can break the inequality. Going from $N=3, R=W=2$ to $N=5, R=W=2$ gives $4 > 5$, which is false: adding replicas silently turned a consistent configuration into an inconsistent one. This is a real operational footgun during cluster expansion, and it is why replication factor changes in Cassandra require an explicit review of consistency levels rather than being a pure capacity operation.
Boundary
The theorem assumes a fixed, agreed replica set. Everything hard in practice is in that assumption.
- Membership changes. During a topology change, the old and new replica sets may not intersect. Reconfiguration protocols exist precisely to hand off safely, and getting them wrong reintroduces the disjointness the inequality was supposed to prevent.
- Sloppy quorums. As above: the acknowledging set is not the replica set, and the guarantee lapses.
- Failure detection. Deciding a replica is unreachable is where the asynchronous model bites. A replica declared dead and later resurrected with stale state is not covered by set arithmetic.
- Byzantine replicas. A lying replica can serve an old value while claiming it is current, and intersection does not help because the intersecting node is the liar. Byzantine quorum systems need $R + W > N + f$ and $N > 3f$ (T063), which is the same idea paying the Byzantine premium.
Within those limits the rule is exact and, unusually for this series, actionable without qualification: pick $N$ odd, set $W > N/2$ if writes may conflict, then choose $R$ to spend the remaining budget wherever your read latency hurts most.