hard Quorum is not Linearizability

The mechanism: quorum overlap guarantees intersection, not a global order

With N replicas, a write acknowledged by W of them and a read answered by R of them, picking R + W > N forces the read set and the write's ack-set to share at least (R + W) − N nodes — pure pigeonhole, since two disjoint subsets of an N-node pool cannot together contain more than N nodes. So once a write has genuinely completed (reached W acks), any later read drawn from the same fixed N nodes is guaranteed to touch at least one replica holding that write, and a correct version/timestamp comparison across the R responses will surface it. That is the whole guarantee: a completed write is not lost to a subsequent read. It says nothing about what happens while a write is still in flight, nothing about whether two different reads issued around the same moment must agree with each other, and nothing about a global order that every client can trust — which is exactly what linearizability demands: that the system behaves as if there were a single copy of the data, and every operation takes effect atomically at some point between its invocation and its completion, in an order consistent with real time.

Counterexample (a): concurrent write + read — the answer depends on which nodes you hit, not on real time

Traced example: N=3 {A, B, C}, W=2, R=2. Key x starts at v1 on all three replicas.

1. t1 — write begins. Client 1 issues SET x=v2; the coordinator sends it to A, B, and C.
2. t2 — A applies and acks. One of the two acks needed for W=2 is in; the write is not yet complete.
3. t3 — two reads land, concurrently with the write. Read #1 picks quorum {B, C}: neither has applied v2 yet, so both answer v1 → the read returns v1. At the exact same instant, Read #2 picks quorum {A, C}: A answers v2, C answers v1 → comparing versions, the read correctly returns v2.
4. t4 — B applies and acks. W=2 (A, B) is now met; the write is reported complete to Client 1 only now.
5. t5 — C finally catches up and applies v2.

Read #1 and Read #2 ran at the same moment, before the write even completed — and returned different answers, purely because of which 2 of the 3 nodes each happened to query. R+W>N never promised these two reads would agree with each other or with a single global moment at which x “became” v2; it only promises that after the write is complete, a read drawn from the full N will include an up-to-date replica. Whether a value is treated as “the winner” when a read's R responses disagree is decided by version comparison — a vector clock, or a last-write-wins (LWW) timestamp — not by which operation happened first in wall-clock time. LWW is especially dangerous here: with clock skew between nodes, a write can be timestamped earlier than an actually-later write and silently lose the comparison, even though it was the true winner in real time.

Counterexample (b): a write that fails below W is neither committed nor cleanly rolled back

1. Client 3 writes SET x=v3 to A, B, C.
2. A applies and acks. B's disk is full and it cannot apply the write. C is briefly unreachable and never receives it.
3. Only 1 ack (A) < W=2 → the coordinator reports the write as FAILED to Client 3.
4. But A still holds v3 — nothing rolls it back; a typical Dynamo-style quorum store has no two-phase-commit/abort step that undoes a partial write.
5. Later, a read arrives with quorum {A, C}: it sees v3 on A and surfaces it — returning a value the client was explicitly told failed to write. A read with quorum {B, C} would instead return the old value, matching the reported failure.

Whether a “failed” write is visible later is undetermined — it depends entirely on which replicas a later read happens to query, not on any single true/false verdict the system committed to. A linearizable system cannot leave an operation's effect ambiguous like this: an operation either visibly took effect for everyone from some point on, or it never took effect at all.

Counterexample (c): sloppy quorum breaks the intersection entirely

Both counterexamples above assume every read and write is drawn from the same fixed N home nodes. A sloppy quorum relaxes that during a partition or outage: if home nodes are unreachable, the coordinator writes to whatever healthy nodes it can reach instead (hinted handoff), just to collect W acks. That preserves availability and durability — but the W nodes now holding the newest value can be outside the N-node pool a later read draws from, so the pigeonhole argument no longer applies at all: the read set and the write set are no longer guaranteed to overlap, because they were never drawn from the same pool. This failure mode is traced in full, with its own worked example and the hinted-handoff recovery storm it causes, in Failure Under Scale: Hinted Handoff & Sloppy Quorum — the short version is: sloppy quorum turns “R+W>N” from a guarantee into a best-effort heuristic.

So what does “W=2, R=2, N=3” actually buy you?

The common shorthand “R+W>N ⇒ strong consistency” is an overclaim. What it actually gives you is a single, narrow guarantee: a read issued strictly after a write has completed, drawn from the same fixed N nodes, with correct version reconciliation, will observe that write. It does not give you: a defined outcome for operations concurrent with each other, a defined outcome for a write that fails below W, immunity from sloppy-quorum node substitution, or any promise that two different clients' operations are consistent with a single real-time order — which is precisely the definition of linearizability. Reaching genuine linearizability requires an additional mechanism on top of quorum counting: a single-leader replication log that serializes every write through one node, or a consensus protocol (Raft, Multi-Paxos) that makes the “which write committed first” question unambiguous by construction — committing a write only after a majority durably agree on its position in one global log, and serving reads either from the leader or via a read-index/lease scheme that proves no newer committed entry exists.

Judgment: how a senior engineer decides

Quorum (Dynamo-style) vs. consensus (Raft/Paxos/single-leader)

Quorum replication is leaderless: any node coordinates, there is no election, and the system stays available and accepting writes through node failures and partitions (AP under CAP). Its actual guarantee is narrow — “a read sees the latest completed write, once the write is done and nodes are drawn from the same fixed set” — not linearizability. Consensus-based replication (Raft, Multi-Paxos, or a single leader with synchronous log replication) pays real coordination cost — leader election on failure, a majority round-trip before any write is acknowledged, and reduced availability during leader loss (CP under CAP) — in exchange for a genuine, provable global order: every acknowledged write is placed at one position in one log that all replicas agree on, so reads that go through the leader (or a correctly implemented read-index) are linearizable.

When quorum's guarantee is enough

Choose quorum when the workload tolerates the anomalies above: shopping carts, social/activity feeds, product catalogs, session data, telemetry ingestion, DNS-like lookups — places where “this read might be a few hundred milliseconds stale, or might momentarily disagree with another concurrent read” is an acceptable cost for always-on writes and lower latency. Layer read-repair and anti-entropy on top (as any serious quorum store does) so staleness is self-healing, not permanent.

When you need real linearizability

Choose consensus, or a linearizable coordination layer built on it (ZooKeeper/etcd, both Raft/Zab-based), when a wrong or ambiguous answer is worse than added latency or reduced availability: distributed locks and leader election, unique-constraint enforcement (usernames, idempotency keys), compare-and-swap/counter operations that must never double-apply, financial ledgers, and any “did my write actually commit?” question that the application cannot afford to get wrong. The trade-off is explicit: linearizability costs a majority round-trip and reduced write availability during leader failover; quorum buys back availability and latency by giving up the global-order guarantee.

Takeaways

• R + W > N guarantees a read intersects a write's ack-set once that write has completed — it is a set-overlap guarantee, not a global ordering guarantee.
• Concurrent writes and reads, partial writes that fail below W, and sloppy quorum all break the naive “strong consistency” reading of R+W>N — two reads in the same real-time window can legitimately disagree.
• “W=2, R=2, N=3 ⇒ strongly consistent” is an overclaim; real linearizability needs a consensus protocol or single-leader log, not just quorum counting.
• Pick quorum for availability-first, staleness-tolerant workloads; pick consensus when an ambiguous or stale answer is unacceptable.

---

Synthesized from Designing Data-Intensive Applications (Kleppmann, Ch. 5, “Limitations of Quorum Consistency”), the Amazon Dynamo paper, and the Raft consensus paper (Ongaro & Ousterhout). Re-authored/Deepened for this guide.

I just read a lesson on **Quorum is not Linearizability** (System Design) and want to truly understand it. Explain Quorum is not Linearizability from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Teach me **Quorum is not Linearizability** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Quiz me on **Quorum is not Linearizability** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Help me remember **Quorum is not Linearizability** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.