Quorums (R + W > N)

Quorums are a fundamental coordination primitive in distributed systems that enable consistency without a single leader. The core idea is simple: if you write data to enough replicas (W) and read from enough replicas (R), and the sum R + W exceeds the total number of replicas (N), then the set of nodes you read from must overlap with the set of nodes you wrote to. This overlap guarantees that at least one node in your read set has the most recent write. By comparing version numbers or timestamps across the R responses, the client can identify and return the latest value.

The most common quorum configuration is N=3, W=2, R=2. With three replicas, writes wait for two acknowledgments and reads query two replicas. Since 2 + 2 = 4 > 3, there is always at least one node in the intersection. This balanced configuration provides both read and write fault tolerance: the system can tolerate one node failure for both reads and writes. Alternative configurations trade off differently. N=3, W=3, R=1 is read-optimized: reads are extremely fast (single replica) but writes require all three replicas to be available, making writes fragile. N=3, W=1, R=3 is write-optimized: writes are fast (single ACK) but reads must query all replicas and wait for all to respond, increasing read latency and reducing read availability. The choice depends entirely on the workload's read/write ratio and latency requirements.

Sloppy quorums extend the standard quorum model to improve availability during partial failures. In a strict quorum, only the N designated replicas for a key can participate in quorum operations. If fewer than W of those N replicas are reachable, writes fail. A sloppy quorum allows the write to succeed by using non-designated nodes as temporary participants. These temporary nodes store the data with a 'hint' indicating which designated node should eventually receive it -- a process called hinted handoff. When the designated node recovers, the temporary node forwards the data. Sloppy quorums are powerful for availability but break the R + W > N consistency guarantee because the 'N' is no longer the same set of nodes for reads and writes. A read using the designated N replicas may miss data that was written to a temporary node via sloppy quorum.

A common misconception is that quorums provide linearizability. They do not, by themselves. Consider a scenario where a write reaches W=2 of 3 replicas, and a subsequent read queries R=2 replicas, one of which has the new value and one which has the old value. The read detects the disagreement and picks the newer value (correct). But during the brief window between the write completing on the first replica and the second replica, another read might see only the old value on both queried replicas. This race condition means quorum reads can return stale data during concurrent writes. True linearizability requires additional mechanisms: read repair during the read (Dynamo-style), or a full consensus protocol like Raft or Paxos that establishes a total order of operations. Systems like etcd use Raft quorums specifically because Raft provides linearizability, not just quorum overlap.

Imagine a jury of 5 members (N=5) deciding a case. The prosecution needs 3 jurors to agree for a conviction (W=3). The defense can poll 3 jurors to check the verdict (R=3). Since 3 + 3 = 6 > 5, at least one juror in the defense's poll participated in the conviction vote. That juror knows the actual verdict, ensuring the defense always learns the true outcome. If the prosecution only needed 1 juror (W=1), the defense would need to poll all 5 (R=5) to be sure of finding that one juror, making the check much slower. This is the quorum trade-off: requiring more agreement at write time (W) reduces the number of checks needed at read time (R), and vice versa.