Majority Quorum
Understanding R+W>N — how distributed systems guarantee reads see writes using quorum overlap.
How Many Nodes Must Agree?
In a replicated storage system, writes go to some nodes while reads may hit different nodes. Without coordination, a read might miss a recent write entirely.
The question: How many nodes must participate in writes and reads to guarantee consistency?
- Replicas may have different values at any moment
- Network delays mean not all nodes update simultaneously
- Need a rule that guarantees reads see writes
Majority = ⌊N/2⌋ + 1
The solution: require a majority of nodes for operations. With N=5 nodes, majority is 3. The key insight: any two groups of 3 nodes from a set of 5 must share at least 1 node.
This is the pigeonhole principle — there aren't enough nodes for two majorities to be completely separate.
- Majority quorum:
⌊N/2⌋ + 1 - N=3 → 2, N=5 → 3, N=7 → 4
- Two majorities always overlap
- Overlap guarantees information transfer
Write to W Nodes
When writing, wait for acknowledgment from W nodes before returning
success. These W nodes form the "write quorum" — they definitively have the
latest value.
The write isn't considered complete until W nodes confirm.
- Write quorum W: Nodes that must acknowledge
- Typically W = majority for strong consistency
- Remaining nodes update asynchronously
- Write fails if fewer than W nodes available
Read from R Nodes — Overlap Guaranteed
When reading, contact R nodes and return the latest version
seen. If
R + W > N, at least one node must be in both the read and
write quorums.
That overlapping node has the latest write, so the read will see it.
- R + W > N ensures overlap
- Minimum overlap = R + W - N nodes
- Read returns highest version among responses
- Read repair can update stale nodes in background
Tunable Consistency
The R+W>N formula lets you tune the trade-off:
- Strong consistency (R=3, W=3): Every read sees every write, but operations are slower (wait for 3 nodes)
- Eventual consistency (R=1, W=1): Fast operations, but reads may miss recent writes
Choose based on whether your application can tolerate stale reads. Some systems allow configuring R and W per-operation for different consistency levels.