Quorums, Repair & Anti-Entropy

The overlap argument

With N replicas, W acknowledgements required to call a write successful, and R responses required to serve a read:

If R + W > N, the read set and the write set cannot be disjoint. They must share at least one node, and that node holds the latest write.

It's the pigeonhole principle. Two subsets of an N-element set with sizes summing to more than N must intersect.

Play with it — kill replicas, change R and W, and watch when reads go stale:

Two things worth doing in the simulator:

Set N=5, W=3, R=2. That's 5, which is not greater than 5 — and the staleness figure is 10%, not zero. The condition is strictly >, and the off-by-one is a genuinely common mistake. R + W = N gives you nothing.

Set W=N and R=1. Staleness drops to zero and reads become a single fast hop — but the "node losses writes survive" stat drops to zero too. Any single failure blocks all writes. That's the real tradeoff the formula hides.

Choosing R and W

The general shape: W and R trade write availability against read availability, and their sum trades both against staleness. N=3/W=2/R=2 is the common default because it tolerates one failure on both paths.

There's also a latency consequence that the availability numbers don't show. A quorum operation's latency is the latency of the W-th fastest replica, so raising W pushes you further into the tail of the response-time distribution. This is why W=N is slow in a way that averages don't reveal — you're waiting for the slowest node every single time.

The mitigation is hedged requests: send to more replicas than you need and take the first W to answer. You pay extra load to cut tail latency, and at high percentiles the trade is usually worth it.

Three ways R + W > N stops protecting you

Back to the hook. The arithmetic is fine; the assumptions underneath it are what break.

1. Sloppy quorums. In a strict quorum, the W nodes must come from the key's designated home replicas. Under a partition, those specific nodes may be unreachable — so Dynamo-style systems accept the write on whatever nodes they can reach, storing a hinted handoff: "I'm holding this for node C; deliver it when C returns."

This keeps you writing during a partition, which is the point. But the write didn't land on the home replicas, so a subsequent read of R home replicas can miss it entirely. Sloppy quorums increase durability and availability, and void the overlap guarantee.

2. Concurrent writes. The overlap guarantee says a read will see the latest write. It does not say what "latest" means when two writes happened concurrently. Two clients writing different values to different quorums both succeed, and now some replicas have one value and some the other. You need version vectors or last-write-wins to resolve it — and as clocks covered, LWW discards data.

3. Failed writes are not rolled back. If a write reaches 1 node but needed 2, the client gets an error — and the node that took it keeps it. There's no rollback. A later read may return a value from a write that was reported as failed. This is deeply counterintuitive and absolutely real.

Keeping replicas converged

Since replicas drift, something must pull them back together. Two mechanisms, and you want both:

Read repair — during a read, the coordinator notices a replica returned an old version and writes the current one back. Free, since you already did the read, but it only ever repairs data that someone reads. Rarely-read keys drift indefinitely.

Anti-entropy — a background process comparing replicas and reconciling differences. This covers the cold data read repair never touches.

The obvious implementation of anti-entropy — send every key and hash to your peer — is unaffordable. The standard solution:

Merkle trees. Build a binary tree where leaves are hashes of key ranges and each internal node hashes its children. To compare two replicas:

1. Exchange root hashes. If equal, the replicas are identical — one hash comparison for the whole dataset.
2. If they differ, exchange the children's hashes and recurse only into subtrees that differ.
3. Continue until you reach the differing leaves.

Comparing two replicas holding a billion keys with three differences takes roughly 3 × log(n) hash comparisons rather than a billion. This is why Merkle trees appear in Cassandra, DynamoDB, Riak, and (for entirely analogous reasons) in Git and blockchains.

Tunable per operation

Real quorum systems let you set consistency per query, which is the practical payoff of all this. In Cassandra terms:

• ONE — fastest, most available, weakest.
• QUORUM — majority of replicas. QUORUM for both reads and writes gives overlap.
• LOCAL_QUORUM — majority within the local datacenter. The important one for multi-region: you get overlap locally without paying a cross-ocean round trip on every operation, at the cost of no cross-region guarantee.
• ALL — strongest, and unavailable the moment any replica is down.

Mapping to earlier lessons: this is PACELC's "else" branch made into a runtime flag. Same data, same cluster, different tradeoff per query.

What to take away

• R + W > N forces overlap. It is strictly greater than — R + W = N buys nothing.
• W and R trade write against read availability; quorum latency is that of the W-th fastest replica, so high W means living in the tail.
• Sloppy quorums, concurrent writes, and un-rolled-back failed writes each defeat the guarantee.
• Quorums bound staleness. Linearizability needs consensus.
• Read repair fixes what's read; anti-entropy fixes what isn't. Merkle trees make the comparison logarithmic.
• Set consistency per operation; LOCAL_QUORUM is usually the right multi-region default.