Quorum Intersection and the Arithmetic of Stale Reads

A leaderless store is configured with three numbers: N, the number of replicas holding each key; W, the number of acknowledgements a write requires; and R, the number of responses a read requires. The inequality R + W > N is presented as the condition for strong consistency. It is a necessary condition for a much narrower property, and knowing exactly which property matters because the label is routinely applied to guarantees the arithmetic does not deliver.

The pigeonhole argument

Take N = 3, W = 2, R = 2. A write succeeds once two replicas have stored it. A read consults two replicas. Any two-element subset of a three-element set intersects any other two-element subset in at least one element, because if they were disjoint their union would need four elements. So the read’s replica set and the write’s acknowledgement set share at least one replica, and that replica holds the latest acknowledged value. The read, taking the newest version among its responses, returns that value.

The general statement: with W acknowledgements out of N and R responses out of N, if R + W > N then every read set intersects every write set. The guarantee that follows is that a read observes the most recent write that completed before the read started.

That is the whole of it. The property is “the read sees the latest completed write”, conditional on the replica sets being the ones the write and read actually used. Several assumptions sit inside that condition.

What the inequality does not give

It does not give serializability. Two concurrent writes may be acknowledged by different quorum subsets, and the intersection guarantees only that a later read sees at least one of them, not which. With last-write-wins resolution, one write is silently dropped. With version vectors, the read may return siblings and require a merge.

It does not give linearizability across the whole operation. The read is linearizable only if the coordinator compares versions correctly and if the write’s quorum membership has not changed between the write and the read. A read that starts before a write completes and finishes after it may or may not see the write; that is allowed by the definition of linearizability only if the operations overlap, which they do.

It does not survive a failed write. A write that reached one replica and then failed to reach a second has not completed, but the one replica holds it. A read that consults that replica and another may see the value and treat it as current. The system must therefore distinguish committed from uncommitted data, and most leaderless stores do not: they treat every stored value as readable. A partially applied write can therefore surface in a read even though the client was told the write failed.

It does not survive sloppy quorums. When W replicas are unavailable, hinted handoff lets the coordinator substitute other nodes to reach W. Those substitute nodes are not in the key’s home replica set. A read that contacts the home replicas may not intersect the substitute set at all. The arithmetic R + W > N is computed over the home set, so it does not apply. Sloppy quorums increase availability and remove the intersection guarantee, which is a trade the operator makes explicitly or by leaving a default in place.

The version comparison is the load-bearing part

The pigeonhole argument only establishes that the read receives at least one response from a replica that has the latest write. Turning that into “the read returns the latest value” requires the coordinator to identify which response is latest. If comparison is by wall-clock timestamp, a replica with a skewed clock can report a newer timestamp for an older value, and the coordinator picks the wrong one.

With version vectors, the comparison is exact with respect to observed causality. A response whose vector is dominated is discarded; the surviving value is returned. This is why quorum systems that claim strong consistency pair the arithmetic with causal metadata. The arithmetic guarantees overlap; the metadata guarantees that overlap is usable. The interaction is described in version vectors and conflict detection.

There is a further subtlety when a read returns siblings. The coordinator cannot pick one, so it returns all of them and the client merges. At that moment the read is not returning “the latest value”; it is returning “the set of values that are not dominated by any other”, and the client’s merge defines the answer. A system in this state is not linearizable, because two clients merging the same siblings independently may produce different results unless the merge is deterministic and commutative.

Read-your-writes needs more than a quorum

A session that writes a value and then reads it back needs the read to reach a replica that received that specific write. A quorum read does not guarantee this: the read set intersects the write’s acknowledgement set, but the value returned is the latest one, which is the value just written only if no other write intervened. If another client wrote afterwards, the read correctly returns that newer value — and the first client sees its own write disappear.

That is correct behaviour for a linearizable register and surprising behaviour for a user who expects their own edit to persist. The fix is not a larger quorum; it is session tracking. The client records the version of its own write and the read waits until a replica reports a version at least that new, or the read is routed to a replica known to have it. Both are mechanisms on top of the quorum, not consequences of it. The general shape of these guarantees is covered in session guarantees and read-your-writes.

Choosing the numbers

Given N, the choices trade availability against read cost and write cost:

Configuration	Write availability	Read cost	Guarantee
W = N, R = 1	low; any replica down blocks writes	one response	every completed write is visible to a read
W = 1, R = N	high	all replicas	reads see every acknowledged write
W = R = majority	tolerates minority loss	majority	intersection holds both ways
W + R ≤ N	highest	lowest	no intersection; eventual only

The third row is the balanced choice and the one the inequality is usually about. For N = 3 that means W = R = 2: writes tolerate one replica down, reads tolerate one replica down, and any read intersects any write.

The fourth row is not a mistake; it is the configuration for workloads that want minimum latency and can tolerate stale reads. It is chosen deliberately when the data is a cache, a counter whose exact value is not actionable, or a feed where staleness is measured in seconds and irrelevant.

The first row is worth noting because it inverts the usual intuition. Requiring every replica for writes makes reads cheap and single-response, but it means a single failed replica blocks all writes to the key. Availability of writes is N - W + 1 replicas’ worth of tolerance, so W = N tolerates zero.

Quorums do not fix partitioning

If the network splits into two halves of a three-replica set, one side has two replicas and the other has one. With W = R = 2, the majority side serves both reads and writes. The minority side cannot complete a write, and a read there returns whatever single replica holds, which may be stale. A client connected to the minority side sees an outage of writes and possibly stale reads. This is the availability cost of the intersection guarantee, and it is not avoidable while keeping the guarantee: the minority side cannot distinguish “the other side is down” from “I am partitioned”, and cannot safely proceed without a majority.

A system that lets the minority side continue is choosing availability and abandoning intersection. That is a legitimate choice — it is what multi-leader replication does — but it changes the consistency model, and the change should be visible in the configuration rather than discovered during an incident. The topology-level version of this trade is in replication topologies and failure models.

The honest label

R + W > N gives read-your-writes-after-completion only under a fixed replica set, exact version comparison, no sloppy quorums, and no partially applied writes being readable. Systems that satisfy all four are usually described as providing strong consistency for single-key operations, which is accurate but narrow: it says nothing about multi-key operations, nothing about ordering between concurrent writes, and nothing about what happens during a partition.

The useful way to hold the arithmetic is as an intersection condition, not a consistency level. It states that the read and the write sets overlap. Everything else — what the overlap is worth — depends on the metadata carried in the values and on whether the coordinator’s comparison is sound.