Quorum systems

Drag R and W. Notice: some combinations guarantee that any read quorum and any write quorum you could pick are forced to share at least one node. Others leave a gap — a read could land entirely on nodes the write never reached.

A quorum system replicates to $N$ nodes and requires a write to succeed on $W$ of them, a read to be answered by $R$ of them. Reads and writes are safe together exactly when:

• $N$ — total number of replicas.
• $W$ — how many replicas a write must reach before it's considered done.
• $R$ — how many replicas a read must query before it returns an answer.

1. Why the inequality works

   Out of $N$ nodes, a write quorum covers $W$ of them and a read quorum covers $R$ of them. If $R + W > N$, there simply aren't enough "empty" slots left for the two quorums to avoid each other — by the pigeonhole principle they must share at least one node.

2. That shared node is the guarantee

   Whatever node sits in the overlap has the latest write, because the write quorum included it. So any read quorum is guaranteed to see it too.

Watch the readout compute $R + W - N$ directly — the overlap margin. Positive means safe, zero or negative means a read and a write could pick disjoint sets of nodes and a stale read slips through.

$N = 5$, and you choose $R = 3$, $W = 3$:

1. Pick concrete quorums

   Label the replicas 1–5. Say the write quorum is $\{1, 2, 3\}$ and the read quorum is $\{3, 4, 5\}$.

2. Find the overlap

   They share node $3$ — whatever the write left there, the read sees it.

3. Check the margin

   $$R + W - N = 3 + 3 - 5 = 1$$

   A margin of exactly 1 means every possible pair of a 3-node read quorum and a 3-node write quorum out of 5 shares at least one node — not just this particular pair.

4. Contrast with an unsafe choice

   $R = 2, W = 2$ gives a margin of $2 + 2 - 5 = -1$: a read quorum like $\{4, 5\}$ and a write quorum like $\{1, 2\}$ share nothing, so the read could miss the write entirely.