Quorum Intersection and Why R + W Must Exceed N

A replication group with N members accepts a write when W of them acknowledge and serves a read when R of them answer. The condition that makes this useful is $R + W > N$: the read set and the write set must overlap in at least one member. Without the overlap, a read can be answered entirely by members that never saw the write, and the value it returns is stale by construction rather than by misfortune.

The inequality is easy to state and easy to misapply, because it constrains the sets, not the counts. Two reads of size R can be disjoint from each other, and a write of size W can overlap a read in exactly one member whose copy is itself behind. The arithmetic gives a guarantee about the most recent successful write only, and only when the sets are chosen with some care.

The overlap argument

Suppose N = 3, W = 2, R = 2. A write reaches two members and is acknowledged. A later read contacts two members. The two sets are subsets of a three-element universe, each of size two, so their intersection is non-empty: at least one member holds both the write and the read request. If the members are honest and the write is ordered before the read, that member can return the newer value, and the read can pick it out if it can tell which value is newer.

Telling which value is newer is the part that requires a version. A timestamp from a loosely synchronised clock is a version with a failure mode; a logical counter per key, incremented by the coordinator, is a version with a different one: two coordinators incrementing concurrently produce the same counter for different values, which is a conflict rather than a stale read. The usual resolution is a version vector or a Lamport-style counter carried with the value, so a read can order the responses it receives and choose the maximum, with ties treated as concurrent writes requiring application-level merge or last-writer-wins with its known anomalies.

The overlap gives a lower bound on freshness, not a proof of it. If the write’s W acknowledgements were collected from members that then crashed before the read, and the read’s R members include the one member that did not receive the write, the read sees the old value. The guarantee is that the read could have seen the new value, not that it will, unless the read set is required to include the specific member that acknowledged. Some designs make that requirement explicit by recording the acknowledging members with the value and requiring the read to contact at least one of them, which turns the probabilistic overlap into a deterministic one at the cost of a larger read set.

N = 3
W = 2   write acknowledged by {A, B}
R = 2   read served by {B, C} -> overlap {B} -> can observe the write
R = 2   read served by {C, A} -> overlap {A} -> can observe the write
R = 1   read served by {C}    -> overlap {} -> stale by construction

The block is the whole argument in five lines. With R = 1 and W = 2, the read has no guaranteed overlap, so a single-member read is a read at whatever freshness that member happens to have. A store that offers a session guarantee of self-consistent reads with R = 1 is relying on the client sticking to the same member, or on the write having reached every member before the read, both of which are outside the quorum guarantee.

Choosing R and W for the workload

The pair is chosen against two competing costs. Raising W makes writes slower and less available, because more members must be up. Raising R makes reads slower and less available for the same reason. The symmetric choice $R = W = \lceil (N+1)/2 \rceil$ minimises the maximum of the two for a given N and tolerates the loss of $N - \max(R, W)$ members for both operations. With N = 3 that is R = W = 2, tolerating one failure. With N = 5, R = W = 3, tolerating two.

The asymmetric choices trade one operation against the other. W = N and R = 1 makes writes maximally durable at the moment of acknowledgement, every member has the value, and reads maximally cheap, because any member will do. This is a common configuration for data that is written once and read many times, where write latency is not on a critical path. W = 1 and R = N makes writes fast and reads expensive, which suits a write-heavy ingest path whose readers can afford to gather every copy.

The unavailable fraction is not symmetric even when the counts are. A write at W = 2 of N = 3 fails if two members are down; a read at R = 2 fails under the same condition. But writes are usually retried by the client and reads are usually on a latency budget, so the practical effect of the same failure tolerance differs.

Sloppy quorums and hinted handoff

The strict quorum assumes the R and W members are drawn from the N designated replicas. A network partition makes that impossible: the designated replicas may be split across the partition, and one side may hold fewer than W of them. A store that refuses writes on that side is consistent and unavailable; a store that accepts writes on whichever members are reachable is available and has weakened the guarantee.

The weakened form is a sloppy quorum: the first W reachable members in a preference list accept the write, even if they are not the designated replicas for that key. The write is stored with a hint that says which replica it belongs to, and the hint is replayed to the real replica when it becomes reachable. This is hinted handoff. The value survives and the system stays writable, but $R + W > N$ no longer holds, because the read set and the write set are not drawn from the same N. A read during the partition can return a value older than the one the sloppy quorum acknowledged.

This is the trade the Dynamo design makes explicitly, and the reason it is described as an availability-first store with eventual consistency rather than a quorum store. The quorum arithmetic is a consistency mechanism, and sloppy quorums are the point at which the mechanism is suspended to preserve availability. Calling such a system “quorum-based” without saying which mode it is in describes the happy path only.

Read repair and the cost of convergence

When a read contacts R members and finds divergent versions, it can repair the divergence by writing the newest value back to the members that returned stale ones. This is read repair, and it converts reads into a background convergence mechanism at no extra round trip in the common case, because the responses are already in hand.

Read repair only touches the keys that are read. A key that is never read after a divergence stays divergent until something else finds it, which is the argument for a periodic anti-entropy pass that compares whole ranges rather than individual keys. The two mechanisms are complementary: read repair is cheap and targeted, anti-entropy is expensive and exhaustive, and a store that relies on one alone either leaves cold data divergent or spends its background bandwidth on data nobody reads.

The repair also has to be careful about which version it propagates. If the read’s R members include one that is mid-write, the “newest” version it returns may be an uncommitted value, and repairing it to the other members makes an uncommitted write durable by accident. Quorum writes avoid this by treating a value as visible only after W acknowledgements, but a read that touches a member holding a partially applied write must be able to distinguish it, which means the version must carry enough state to say whether it is committed. A bare timestamp does not.

Where the arithmetic stops applying

Quorum intersection is a per-key argument. It says nothing about operations that span keys, which is the reason multi-key transactions need a different mechanism: two-phase commit, or a consensus protocol over the participant set. A store can have perfect per-key quorum consistency and still allow a transaction that reads one key and writes another to observe an inconsistent snapshot.

It also assumes the members that acknowledge are the members that hold the value. A member that acknowledges a write into a volatile buffer and crashes before persisting it has acknowledged a value it does not have, and the read set’s overlap with the write set is then an overlap with a member that lost the data. The fix is on the write path: acknowledge only after the value is durable on that member, which is a per-member fsync or its equivalent, and which is why W-way replication latency is dominated by the slowest of W durable writes rather than by network round trips. The relationship between acknowledgement and durability is the same one that governs the rebuild window after a failure, and it is the reason a store’s stated quorum parameters are only meaningful alongside its stated acknowledgement semantics.