Majority Quorum

Understanding R+W>N — how distributed systems guarantee reads see writes using quorum overlap.

Read this as How do reads overlap writes so stale values are bounded?
Failure Trap
Choosing R and W independently, then discovering reads can miss committed writes.
Decision Rule
For strong quorum reads, keep R + W greater than N; relax only when stale reads are an explicit product choice.
Majority quorum: how R plus W greater than N works Five replica nodes shown as circles. The animation steps through the problem of disagreeing replicas, the majority rule that any two groups of three out of five must share a node, a write quorum of three nodes, a read quorum that overlaps the write quorum in exactly one node so the read sees the latest value, and the trade-off between strong and eventual consistency. Which value is correct? R1 v1 R2 v2 R3 v1 R4 v2 R5 v1 Client reads 1 node gets v1 or v2 Reads can miss the newest write Majority = ⌊N/2⌋+1 = 3 R1 R2 R3 R4 R5 Majority = 3 of 5 Pigeonhole principle: two groups of 3 must share ≥ 1 node Write to W = 3 nodes Write quorum W = 3 R1 X R2 X R3 X R4 old R5 old Client writes X Done only when 3 confirm R + W > N → overlap W = 3 R = 3 R1 R2 R3 R4 R5 R3 is in both quorums 3 + 3 > 5 ≥ 1 shared node has the write Tunable consistency Strong · R=3 W=3 3+3>5 ✓ overlap → fresh Eventual · R=1 W=1 1+1<5 ✗ no overlap → stale risk in W overlap (W∩R) Pick latency vs freshness
1 / ?

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.

Here the write quorum is {R1, R2, R3} and the read quorum is {R3, R4, R5}. They share exactly one node — R3 — and that node holds the latest write, so the read is guaranteed to see it.

  • R + W > N ensures overlap
  • Minimum overlap = R + W − N = 1 node
  • 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.