The Limits of Quorum Consistency
On this page6
The previous post derived the quorum condition: with n replicas, if every write is acknowledged by w of them and every read queries r of them, then w + r > n forces the read set and the write set to share at least one node. That node has the latest value, so the read sees it.
The derivation is sound. The conclusion people take from it — that a quorum read returns the current value — is not. w + r > n is better understood as a dial that lowers the probability of reading stale data, and it is worth being precise about how much it actually buys.
What the Overlap Actually Promises
The guarantee is narrow and worth stating exactly: the set of nodes you read from and the set of nodes you wrote to have at least one node in common. Nothing more.
r and w are usually set to majorities — more than n/2 each — because that satisfies the condition while tolerating up to n/2 node failures. But majorities are a convenience, not a requirement. Any assignment where the read and write sets must overlap works, and distributed algorithms exploit that flexibility.
You can also go the other way deliberately and set w + r ≤ n, breaking the condition on purpose. Reads and writes are still sent to all n nodes; you simply require fewer successful responses before declaring success. Stale reads become more likely, and in exchange you get lower latency and better availability: during a network interruption, more replicas can be unreachable before the database stops accepting operations at all. The system only becomes unavailable once fewer than w or r nodes can be reached.
That is a legitimate configuration. It is a decision to trade freshness for uptime, and Dynamo-style databases exist largely to make it available.
Where It Breaks Anyway
The more interesting point is that even with w + r > n holding, there are several ways to read a stale value.
A sloppy quorum removes the overlap. If writes were accepted on nodes outside the designated n — which is what a sloppy quorum does during a partition — then the write set and the read set are no longer drawn from the same pool, and the arithmetic stops applying. The next post is entirely about this trade.
Concurrent writes have no defined order. If two writes happen concurrently, “the latest value” is not a well-formed idea. The quorum will faithfully return a recent write; which one is undetermined. Two posts on deal with what “concurrent” actually means and what a database can do about it.
A read can race an in-flight write. A write that is still propagating has reached some replicas and not others. A read landing in that window may return the old value or the new one, and both are legitimate outcomes.
Write during propagation: concurrent read sees stale data
A failed write is not rolled back. This is the one that surprises people. Suppose a write succeeds on two replicas and fails on the rest, so it did not reach w and the client is told the write failed. The database does not undo the copies that did succeed. Those replicas are now holding a value from a write that was reported as failed — and subsequent reads may return it. A failed write is not the same as a write that did not happen.
Restoring a node can break the invariant. If a replica holding the new value dies and is rebuilt from a replica holding an old one, the number of replicas carrying the new value can quietly drop below w. The quorum condition was satisfied when the write was acknowledged and is not satisfied any more.
None of these are bugs. They are the honest behaviour of a system tuned for availability, and the parameters let you adjust the odds rather than eliminate the cases.
The Guarantees You Don’t Get
There is a sharper way to say all of this, and it connects directly back to the problems this series spent two posts on.
| Guarantee | Meaning | From a quorum? |
|---|---|---|
| Read-your-writes | you always see your own writes | ✗ |
| Monotonic reads | you never see time move backwards | ✗ |
| Consistent prefix reads | you never see an effect before its cause | ✗ |
| Read/write set overlap | at least one node you read has the latest write | ✓ |
A quorum gives you the last row and none of the ones above it. Every anomaly from the replication lag posts — submitting a comment and not seeing it, refreshing and watching a value go backwards, reading a reply before the message it answers — can still occur under w + r > n.
This is worth internalising because the arithmetic feels like it should imply the others. It doesn’t. Those guarantees require ordering across operations, and a quorum only constrains set membership for one operation at a time. Getting them back means transactions or consensus, which is a different chapter of the story.
Monitoring Staleness
If freshness is a probability rather than a guarantee, the operational question becomes: how stale is this database right now? For leader-based replication that question has a clean answer, and for leaderless replication it mostly doesn’t.
Leader-based replication applies writes to every node in the same order, so every node has a position in the replication log. Subtract a follower’s position from the leader’s and you have the lag, as a number, exposed as a metric you can graph and alert on.
Leaderless replication has no fixed order in which writes are applied, so there is no position to subtract. The clean number does not exist.
It gets worse if the cluster relies on read repair alone without an anti-entropy process. Read repair only fixes replicas that are actually read, so a rarely-read key can hold an arbitrarily old value indefinitely. There is no upper bound on staleness — not a large bound, no bound.
There has been research into measuring replica staleness and predicting the expected proportion of stale reads from n, w and r, but it hasn’t become standard practice, and most databases don’t ship the metric. Which leaves an uncomfortable gap: “eventual consistency” is a deliberately vague promise, and operating a system on a vague promise is hard. If you cannot quantify the “eventual”, you cannot tell a healthy cluster from one that has been silently drifting for a week.
Absent a real staleness metric, the practical fallbacks are indirect — alert on failed writes, on nodes falling out of the cluster, on anti-entropy jobs not completing — none of which measures the thing you actually care about.
Key Takeaways
w + r > nguarantees exactly one thing: the read set and write set overlap in at least one node. It is a probability dial, not a promise of freshness.- Majorities are the common choice but not a requirement — any overlapping assignment satisfies the condition.
- Setting
w + r ≤ non purpose is a valid trade: more stale reads in exchange for lower latency and tolerating more unreachable replicas. - Even with the condition satisfied, stale reads arise from sloppy quorums, concurrent writes, reads racing in-flight writes, failed writes that are never rolled back, and nodes restored from stale replicas.
- Quorums provide none of read-your-writes, monotonic reads or consistent prefix reads. Every anomaly from the replication lag posts remains possible.
- Leader-based replication measures lag by subtracting log positions. Leaderless has no fixed write order, so that number doesn’t exist.
- With read repair and no anti-entropy, a rarely-read key has no bound on how stale it can be.
- “Eventual consistency” is hard to operate precisely because the “eventual” is rarely quantified.
References
- Martin Kleppmann, Designing Data-Intensive Applications, chapter 5 — the canonical treatment of replication this series works through.
- DeCandia et al. — Dynamo: Amazon’s Highly Available Key-value Store (SOSP 2007).
- Bailis et al. — Probabilistically Bounded Staleness for Practical Partial Quorums (VLDB 2012), on predicting stale reads from
n,wandr. - Apache Cassandra — Dynamo-style architecture, including tunable consistency levels.