Quorum Intersection: Why R + W > N Is Necessary but Not Sufficient

Three replicas, a write that must be acknowledged by two, a read that must consult two. Two plus two is greater than three, so every read set intersects every write set, and a reader always contacts at least one replica that holds the latest write. That reasoning is correct as far as it goes, and it is the reason the inequality R + W > N is quoted so often. It is also insufficient in three separate ways that are worth separating: it does not say the intersecting replica will return the new value, it does not survive concurrent writes, and it does not survive a topology that moves keys around.

What the inequality proves

The proof is a pigeonhole argument over sets. A write acknowledged by W of N replicas occupies a set of size W. A read that contacts R distinct replicas occupies a set of size R. If R + W > N, the two sets cannot be disjoint, since their union would exceed N. The intersection contains at least one replica that saw the write.

Note what the argument requires. The read must contact distinct replicas, not the same one twice. The write and read must be over the same N replicas, not over two different replica sets that happen to be the same size. And the write must have been acknowledged before the read started, otherwise there is nothing to find. All three are assumptions about the client and the topology, not about the data, and each one is routinely violated.

The inequality also says nothing about which value the intersecting replica holds. It holds the write; it may also hold a newer write from a later operation, or an older one. The reader gets a set of R values and must choose. If the write is versioned, the reader can pick the highest version and be correct. If it is not, the reader has R different values and no basis for choosing between them.

Versioning is what makes the intersection usable

A quorum read that returns three values from three replicas is only meaningful if the values are comparable. The standard mechanism is a version stamp attached at write time, monotonically increasing per key. The reader takes the maximum version present and returns it. Concurrent writes produce the same version on two replicas, which is a genuine conflict requiring a merge, not a tie to break arbitrarily.

Two version schemes are common and they differ in what they can express.

A per-key counter incremented on every write is simple and sufficient when writes for a key are serialised by a single coordinator. It fails when two coordinators write concurrently: both produce version 5, and the reader cannot order them.

A vector clock carries one counter per coordinator. Two writes are comparable if one dominates the other on every component, and concurrent if neither does. The reader can distinguish “replica B is behind” from “two writers disagreed”, which the scalar counter cannot. The cost is size: a vector clock grows with the number of writers that have touched the key, and a key written by many short-lived clients accumulates a large stamp. Bounding that growth requires dropping entries, and dropping an entry can make a concurrent write look ordered.

Dynamo’s design made this trade explicitly and its descendants inherited the consequence: the system returns multiple versions and the application resolves them, or a last-write-wins rule collapses them by timestamp and loses one of the writes. The timestamp rule is a decision to discard data, and it is a reasonable decision for a shopping cart and an unreasonable one for a ledger.

Concurrent writes are not a quorum problem

Suppose two clients write the same key at the same time, each to a different coordinator, each achieving W acknowledgements. Both writes succeed. The quorum condition held for both. There is now no single latest value, because there was never an order between the two writes. The intersection property guarantees the reader sees one of them, and no choice of R and W can make it see a value that never existed.

The fix for this is not a larger quorum. It is either a coordination point that serialises the writes — a leader, or a lock, or a consensus round — or a conflict resolution rule applied at read or write time. Raising W to N does not help: it prevents the two writes from both being acknowledged only if the replicas refuse to accept conflicting writes, which requires them to compare versions, which is the resolution rule again, applied on the write path.

This is the reason quorum systems are described as “tunable consistency” rather than as strong consistency. The tuning moves the probability that a read misses a recent write, and it moves nothing about the ordering of concurrent writes. The ordering is supplied by the topology, not the arithmetic.

Sloppy quorums and the N that is not fixed

The inequality assumes the write lands on the same N replicas the read consults. Real clusters move data. A node is down, a partition isolates a rack, a rebalance migrates a range. The response in Dynamo-style systems is a sloppy quorum: if fewer than W of the preferred replicas are reachable, the write is accepted by other nodes in the cluster and tagged for later handoff. The write succeeds, availability is preserved, and the set of nodes holding it is no longer the preferred set.

Now the reader contacts the R preferred replicas and finds nothing, because the write is parked on three nodes elsewhere. R + W > N is satisfied on paper and violated in fact, since the write set and the read set are drawn from different populations. The remedy is hinted handoff: the parking nodes forward the write to the preferred replicas when they return, and the read path may also consult a wider set. Both remedies are asynchronous, so the anomaly window is the handoff delay, not a fixed bound. Anti-entropy repair is what recovers the writes whose hints expired before they could be delivered.

Sloppy quorums are a deliberate exchange: the system accepts writes during a partial outage and gives up the intersection guarantee for the duration. Whether that is correct depends entirely on what the read is for. A write that must be visible to a specific reader — a user’s own update — cannot tolerate it. A write whose absence is tolerable for a bounded period can.

preferred replicas for key k:  {A, B, C}      N = 3
W = 2, R = 2                                  R + W = 4 > 3

A and B unreachable.
write(k) -> sloppy: accepted by {D, E}, tagged for handoff to {A, B}
read(k)  -> {A, B, C}: C has no value, A and B are down
            intersection is empty despite the inequality holding

The failure is not arithmetic; it is that the two operations were performed over different replica sets. Any implementation offering sloppy quorums has to say so, because a client that assumes the inequality is enforced over a fixed set will read stale data with no signal that it did.

Per-key quorums and the cluster-wide picture

Even with a fixed replica set per key and strict quorums, the guarantee is per key. A cluster of a hundred nodes partitioned into shards has a quorum per shard, and two keys on different shards have no ordering relation at all. A transaction that writes two keys with per-key quorums can be acknowledged with one write durable and the other lost, and no amount of R and W tuning changes that.

That is the gap that cross-shard protocols fill, and the reason two-phase commit exists as a separate mechanism rather than as a parameter of the quorum. It is also why the guarantee is described as “linearizable per key” rather than linearizable, when it is described precisely at all.

The other cluster-wide effect is that quorum sizes interact with the failure domain. A quorum of two out of three replicas tolerates one failure only if the three are in different failure domains. If all three sit in one rack, the rack’s power failure removes all three and the quorum is irrelevant. Placing replicas across racks or zones is what makes the arithmetic mean something.

The placement also has to match the intended failure model in its counts, and this is where configurations go wrong quietly. Five replicas spread 3/1/1 across three zones give a majority of three that can be formed entirely inside the first zone: the loss of that zone leaves two replicas, which is not a majority, even though two zones are still up. A 2/2/1 spread with the same five replicas survives any single zone loss, since the two survivors hold four. The general condition is that the replicas outside the f largest domains must number at least Q, the quorum size. A placement that looks balanced but violates it provides no tolerance for the failure it was designed for, and the defect is invisible until that domain fails.

Where a full replica per domain is too expensive, a witness — a voting node that holds no data — lets two data replicas plus one arbiter form a three-voter quorum across three domains. It converts a two-copy configuration from “no majority possible” into “one failure tolerable”, at the cost of running on a single copy until the lost replica is replaced. Witnesses also have to be placed in their own domain; a witness sharing a rack with a data replica adds nothing.

Reading the guarantee honestly

The practical summary is a list of what a quorum does and does not buy.

It buys a bound on staleness relative to acknowledged writes, conditional on a fixed replica set, distinct reads, and versioned values. It buys tolerance of a minority of node failures, conditional on those failures being independent. It buys availability during a minority outage, if the implementation allows sloppy quorums, at the cost of the first guarantee.

It does not buy serialisation of concurrent writes. It does not buy cross-key atomicity. It does not buy protection against correlated failure. And it does not buy any statement at all about reads served from a cache, a materialised view, or a secondary index that was itself replicated with different parameters.

The last point is the one that catches people. A secondary index maintained asynchronously has its own lag, and a query that uses it performs a quorum read of the index and then a quorum read of the rows. Each read is individually consistent with respect to its own replica set, and the pair is not consistent with respect to each other: the index may point at a row version that has since changed, or at a row that no longer exists. The composition of two quorum reads is not a quorum read, which is why systems that offer secondary indexes with a consistency claim have to route those queries differently.