Skip to content

Quorum Read/Write Protocol

Read/write protocol — instantiates Shared-State Consistency Contract Design

Writes touch W replicas and reads touch R of N so the two sets always overlap (R + W > N), turning consistency, latency, and availability into three tunable dials.

Quorum Read/Write Protocol is a leaderless design in which a write is accepted once W of the N replicas acknowledge it and a read gathers responses from R replicas and returns the newest version among them. Its defining idea is a piece of set arithmetic: if R + W > N, every read quorum necessarily overlaps every write quorum, so a read is guaranteed to touch at least one replica carrying the most recent acknowledged write. There is no distinguished authority — replicas are symmetric — and the guarantee is not fixed but chosen, by picking R, W, and N. That tunability is the whole point: the same protocol can lean toward freshness or toward speed and availability depending on how the three dials are set.

Example

A globally used app stores user preferences in a Dynamo-style key-value store with N = 3 replicas per key. The team sets W = 2 and R = 2: a preference change is acknowledged once two replicas persist it, and a read consults two and keeps the version with the higher token. Because 2 + 2 > 3, any read overlaps any write — a change is visible to the next read even if one replica missed it. Under pressure to cut read latency, an operator drops to R = 1: reads now hit a single replica and return fast, but 1 + 2 is not greater than 3, so a read can land on the one replica that missed the write and silently return the old preference. The dial moved the contract, quietly — which is exactly the failure the archetype warns about, made visible here as a number the team chose.

How it works

The mechanism is the R + W > N invariant plus a rule for picking a winner among the R responses (highest version token wins; concurrent versions are surfaced, not silently merged). Everything else — sloppy quorums, hinted handoff — is a deliberate relaxation of that invariant to stay available when replicas are down, and each relaxation trades away the overlap guarantee for uptime. Reads routinely discover that some of the R replicas are stale; healing those laggards is handed to a repair procedure rather than done here.

Tuning parameters

  • N (replication factor) — more replicas spread load and survive more failures, at higher storage and write cost.
  • W (write quorum) — raising W widens overlap and durability but slows and endangers writes when replicas are down.
  • R (read quorum) — raising R improves the odds of seeing the freshest value at the cost of read latency.
  • Overlap stance — insist on R + W > N (freshness guaranteed) or relax it for speed, accepting possible stale reads.
  • Sloppy quorum / hinted handoff — accept writes on substitute replicas during faults to stay available, at the price of temporarily breaking the overlap guarantee.

When it helps, and when it misleads

Its strength is per-workload tunability without a leader bottleneck: a read-heavy path can favor low R, a correctness-sensitive path can widen the quorums, and the system stays available under many partitions. It is operationally simple and degrades gracefully.

Where it misleads is in what overlap actually buys. R + W > N guarantees a read sees the latest acknowledged value; it does not by itself deliver linearizability — concurrent reads can still disagree without a read barrier, and the protocol says nothing about resolving two genuinely concurrent writes.[1] "Sloppy" quorums quietly suspend the overlap guarantee under exactly the failures when people assume it holds. The classic error is citing R + W > N as if it proved strong consistency. The discipline is to state whether overlap holds under the declared fault model, not just nominally, and to pair the read path with conflict detection and repair.

How it implements the components

  • write_acceptance_rule — a write is committed exactly when W replicas acknowledge; the rule for when a write "counts."
  • read_selection_rule — a read consults R replicas and returns the newest version among them; the rule for what a read returns.
  • coordination_latency_and_availability_budget — R, W, and N are the knobs that spend coordination and set the latency/availability trade explicitly.

It does not declare the guarantee level (consistency_guarantee_profile) — that is Linearizable Read/Write Protocol — resolve concurrent writes (conflict_resolution_rule, Multi-Leader Replication with Conflict Resolution), or repair the stale replicas a read finds (recovery_and_reconciliation_path, Read Repair).

Notes

Overlap alone is a value-freshness property, not an ordering one. To approach linearizability with quorums you need a read barrier (an ABD-style write-back on read, or a read-index) on top of R + W > N; without it, two clients reading concurrently during an in-flight write can still observe different values. Treat the quorum arithmetic as necessary, not sufficient.

References

[1] PACELC (Abadi) extends CAP: even with no partition (the "else" case), a replicated store trades latency against consistency. The R/W/N dials are precisely that trade — smaller quorums cut latency and weaken the freshness guarantee. ↩