What Quorum Arithmetic Leaves Out

For three replicas, a read quorumA required set or number of replica responses used by a read or write protocol. of two and a write quorum of two must overlap. The arithmetic is simple: two disjoint groups of two would require four replicas. The consistency claim becomes harder when membership changes or a read observes an unfinished write.

Two small executable models make those assumptions visible. The first changes which replicas can answer. The second keeps membership fixed but removes the read’s write-back phase. Each exposes a different gap between counting responses and implementing an atomic registerConcurrent operations behave as if each took effect at one instant between its start and finish..

What R + W > N proves

Start with a fixed home set A, B, C. A write completes after two replicas have stored version v1. A later read collects two versions and chooses the newest. With no intervening write or loss of acknowledged state, every read sees at least one replica that stored v1.

The general argument is about sets, not clocks: two subsets of the same N-element universe cannot be disjoint when their sizes sum to more than N. The program checks this equivalence for all 140 nonempty quorum-size configurations with 1 ≤ N ≤ 7, covering 21,343 respondent pairs.

Intersection guarantees contact with a replica, while the protocol still has to preserve acknowledged state and select an appropriate version. The completed-write example uses integer version labels and newest-version selection. Those are explicit model rules, not consequences of quorum arithmetic.

Changing the respondent universe

The Dynamo paper describes sloppy quorums: operations use healthy nodes from a preference list, including substitutes when home replicas are unreachable. A substitute keeps a hint identifying the intended replica and later attempts handoff. This favors availability during failures, but the successful respondents need not come from the same home set.

Consider a partition or asymmetric reachability. A write coordinator can reach A, D, E; B and C are unreachable from it. A and fallback D acknowledge v1 while E’s delivery remains delayed, satisfying W=2. A later read coordinator obtains B and C, both still holding v0. Its R=2 also succeeds. The sets {A,D} and {B,C} never intersect.

Enumerating every size-two read/write pair over A through E yields 30 disjoint pairs out of 100. That is a count of structural counterexamples. It is not a 30% stale-read probability: a real routing and failure model determines which pairs occur, how often they occur, and when replication catches up.

Even fixed membership needs a read protocol

Now keep A, B, C and R=W=2. A write of v1 reaches only A and stays pending. Read 1 queries A and B, selects v1, and returns. Read 2 starts after Read 1 finishes, queries B and C, and returns v0. Both reads collected two home replicas.

This history cannot be linearized as an atomic register. Putting the pending write before Read 1 explains v1 but makes Read 2’s v0 impossible. Putting the write later cannot explain Read 1. A quorum intersection involving a completed write does not settle what a read should do with a partially propagated one.

The Attiya–Bar-Noy–Dolev register construction provides the relevant mechanism: after selecting the latest label from a majority, the reader announces it to a majority before finishing. In the model, writing v1 back to A and B before Read 1 returns changes the later B,C read to v1. All nine combinations of majority write-back sets and subsequent read sets pass the same intersection check.

Read the service contract at the routing boundary

These protocol distinctions matter when an application routes storage requests across regions. Current Bigtable replication documentation describes eventual consistency between clusters and read-your-writes behavior with single-cluster routing. Current DynamoDB global-table documentation distinguishes multi-Region eventual consistency from multi-Region strong consistency. The historical Dynamo design is not a substitute for either service’s current contract.

For an agent’s checkpoint store, a retrieved document index, or any shared application state, the useful questions are concrete: Which replicas may answer after failover? What does an acknowledgment preserve? Can a read expose an unfinished write? Does returning that version require write-back? The notebook lets each assumption be changed separately, so a consistency claim can be tied to an executable rule.