Distributed Systems / Under the Hood

Quorums and Stale Reads: What R + W > N Really Guarantees

Understand replica-set intersection, asynchronous replication, failed writes, and the limits of quorum arithmetic. Explore stale reads in a deterministic single-writer lab.

Palash Vij / Published / 3 min read
Source-backed explainer Quorums Replication Consistency Failure

A write succeeds, then a read returns the previous value. That can be expected when a primary acknowledges before every secondary receives the update and the read goes to a lagging copy.

Quorums offer a useful way to reason about overlap, but the arithmetic is not a complete consistency protocol. The conditions behind the formula matter as much as the formula itself.

Start with sets, not slogans

For a fixed replica set of size N, let a successful write reach W replicas and a read consult R replicas. If R + W > N, those two sets must overlap.

With five replicas, a write set of three and a read set of three cannot be disjoint. A write set of two and a read set of two can be. This is a statement about membership, not about how values are ordered or which versions a client may return.

The assumed sets must belong to the same membership configuration. A protocol using fallback replicas, changing membership, or different rules for failure recovery needs a more careful argument.

An overlapping replica is necessary evidence, not a complete answer

The read still needs a rule for recognizing the right value. Concurrent writes, partial writes, version ordering, and failure during acknowledgment complicate the decision. Choosing the largest timestamp is not automatically correct if clocks or ownership rules are unsuitable.

Durability is another dimension. If an acknowledgment precedes persistence and every relevant copy loses volatile state, set overlap cannot reconstruct the lost data.

Linearizability concerns the observable ordering of operations, including their completion times. Proving it requires a protocol argument, not only R + W > N. Leader-based systems also need fencing or terms so an old leader cannot continue acting after replacement.

A failed write can have effects

Suppose the client times out before collecting enough acknowledgments. Some replicas may already contain the new value. “The client did not see success” does not mean “no server applied the write.”

The system needs rules for retries, reconciliation, visibility of incomplete work, and idempotency. This is one reason a retry policy belongs in the storage contract rather than only in a generic HTTP wrapper.

Network partitions add uncertainty: an unavailable peer might be failed or merely unreachable. Failure detection provides information for decisions, not perfect knowledge of remote state.

Explore the restricted model

The Distributed Systems Playground uses a fixed primary, one key, ordered versions, and deterministic logical ticks. Write a new version, read a secondary before delivery, then advance the clock and read again.

Change R and W while keeping N fixed. Fail nodes and observe when a configured operation becomes unavailable. Reset between configurations so the initial state remains clear.

The teaching model acknowledges its first W live replicas and reads its first R live replicas. That deterministic selection is useful for reproducibility but does not explore every possible quorum combination. It does not implement Raft, concurrent writers, durable logs, or automatic membership changes.

Measure behavior, not just success rate

A real experiment should record operation invocation/completion, returned versions, timeouts, retry identities, failures, and recovery events. A high success percentage says little about consistency unless the observed history is checked against the promised model.

Latency and availability tradeoffs also depend on replica placement and failure correlation. Waiting for more responses may expose slower replicas or cross-region delays, but there is no universal numeric penalty to attach to a quorum size.

Use the model to understand overlap, then evaluate a real protocol against its actual guarantees. If the system’s documentation says “eventual consistency,” do not relabel it “strong” because one setting satisfies a familiar inequality.

Further reading

Primary references behind this explanation. Consult documentation for the version and environment you actually run.

  1. Dynamo: Amazon's Highly Available Key-Value Store
  2. Raft: In Search of an Understandable Consensus Algorithm
Follow the thread

Related reading

Search the notebook

Search articles, projects, and experiments. Everything stays on your device.

palash / notebook

A small doorway into the site. No shell, no remote execution.

Welcome. Type help to find your way around.

lab →experience →contact →Ctrl / Cmd + K