Quorum overlap alone does not make reads linearizable

The idea

Leaderless replicated stores keep each key on N replicas. A write succeeds once W replicas acknowledge it, and a read asks R replicas and returns the value with the highest version. If R + W > N, every read set overlaps every write set, so at least one replica in any read has seen the most recent acknowledged write.

That overlap is useful. It lets you tolerate slow or failed nodes without a leader, and it means a completed write is never invisible to a later read that reaches a full quorum.

The common mistake is to read the inequality as a consistency guarantee. It says something about acknowledged writes. It says nothing about writes still in flight, writes that failed halfway, or how two independent readers see the same history.

An example

Take N = 3, W = 2, R = 2, replicas A, B and C, and a key x currently at version 1.

• A writer sends x = 2 to all three replicas. A applies it. The messages to B and C are delayed.
• Reader one queries A and B. It sees version 2 on A and version 1 on B, picks the higher version, and returns 2.
• Reader one finishes. Only then does reader two start, querying B and C. Both still hold version 1. It returns 1.

Every quorum rule was respected. Yet one client observed the new value, and a strictly later client observed the old one. That is a linearizability violation, and code that reads a flag, a balance or a lock owner and acts on it will behave wrongly.

Now suppose the writer times out and reports failure. A still holds version 2. Nothing rolls it back, so the failed write can surface in a later read, or spread through anti-entropy.

Where it breaks

Several common features quietly remove the overlap you were counting on.

• Sloppy quorums with hinted handoff accept writes on nodes outside the key's home replicas during a partition. Reads against the home replicas can miss them entirely.
• Last-write-wins with wall clock timestamps lets a node with a fast clock overwrite newer data. The write was acknowledged and is still lost.
• Concurrent writes to the same key have no single latest value. Without version vectors or a merge rule, one of them disappears.
• Changing replica membership while reads and writes continue can produce read and write sets that do not intersect.

If you need compare-and-set, uniqueness or a correct lock, a quorum store tuned this way is the wrong tool. That workload wants consensus.

In practice

I would start by writing down which guarantee each key actually needs. Most data tolerates brief staleness. A few keys, such as ownership, idempotency records and balances, do not.

• For keys that need linearizable reads, use a consensus-backed store, or make reads write back: before returning, push the chosen value to a quorum. That is the second phase of the ABD algorithm, and it closes the new-then-old gap at the cost of extra latency.
• Disable sloppy quorums for those keys, and accept lower availability during partitions.
• Version with server-assigned counters or version vectors, not client wall clocks.
• Treat a timed-out write as unknown outcome, not failure. Retry it idempotently or read before deciding.
• Test with recorded operation histories under injected partitions and delays, and check them with a linearizability checker. Happy-path tests will not show any of this.

R + W > N promises that a read can find the latest acknowledged write, not that two readers agree on it, so add a write-back read or use consensus wherever that difference matters.