Replication Factor, Read Quorum, Write Quorum, and the Meaning of R + W > N

Learning outcomes

AtlasMart now has replicated state, but the team has started compressing an entire correctness argument into one formula: R + W > N. The formula is useful only when its sets, membership, placement, version ordering, and failure assumptions are explicit. This lesson turns the arithmetic back into a concrete request history.

1. Define N, R, and W as sets, not slogans

Replication factor (N) is the number of intended replicas for the key/range under the stated topology. W is the number of qualifying write acknowledgements required before the coordinator reports success. R is the number of qualifying read responses required before the coordinator can construct a result. Those words hide product-specific details: “qualifying” may mean received, persisted, applied, local-data-center, or another contract. Always read the actual implementation semantics.

For a fixed replica set of size N, if a successful write has an acknowledgement set of size W and a successful read samples a set of size R, then R + W > N means the two sets cannot be disjoint. At least one replica belongs to both sets. That is a pigeonhole/intersection argument.

2. The overlap proof and its assumptions

Assume the preferred replica set for an order is exactly {A,B,C}, so N=3. A write acknowledged by {A,B} has W=2. A later read consulting {B,C} has R=2. Since 2+2>3, the sets overlap at B. If B carries the completed write and versions can be ordered correctly, the read has evidence of that write.

The conclusion becomes weaker when any premise changes. If the successful write was stored on a fallback node outside the original three, a later read from recovered preferred replicas may have no intersection with the actual write acknowledgement set. If two writes are concurrent, “highest timestamp wins” can discard one even though read and write sets overlap. If membership changes between operations, the old algebra may refer to different populations. If a stale node has not been repaired, low-R reads can still miss recent state.

3. Strict quorum and sloppy quorum are different set systems

A strict quorum design counts members of the designated replica set. Dynamo-style sloppy quorum improves availability by contacting the first N healthy nodes in a preference list, potentially storing a hinted copy outside the normal home set. The original Dynamo paper calls its result “quorum-like” for exactly this reason. Hinted handoff later tries to restore normal placement.

This availability mechanism is valuable, but it means an engineer cannot take the fixed-set proof, ignore the placement change, and claim a guarantee that depends on actual overlap. The correct operational question is: which nodes acknowledged this version, which nodes are eligible for the later read, and how are divergent versions detected and reconciled?

4. Deliberately wrong approach — treat R + W > N as automatic strong consistency

AtlasMart uses N=3,R=2,W=2 and writes during a partition to C plus fallback D. Later A and B recover before hinted handoff/repair. A read from A and B satisfies the numeric R=2, but those two responses contain only the old version. The arithmetic still says 2+2>3; the actual acknowledgement and read sets are disjoint because the write placement changed.

The repair is to document strict versus sloppy membership, version semantics, handoff/repair behavior, and the exact consistency property the client needs. If an invariant truly requires linearizable single-object updates, use a mechanism that explicitly provides that property under its stated failure assumptions rather than deriving it from a marketing shorthand.

5. AtlasMart lab — make overlap visible

The simulator prints the actual write and read sets. First it demonstrates fixed-set intersection. Then it moves a successful write to a fallback replica and shows why the same arithmetic no longer proves actual overlap.

from dataclasses import dataclass

@dataclass(frozen=True)
class Version:
    value: str
    version: int

replicas = {"A": Version("AUTHORIZED", 7),
            "B": Version("AUTHORIZED", 7),
            "C": Version("AUTHORIZED", 7),
            "D": Version("AUTHORIZED", 7)}
N, R, W = 3, 2, 2
new = Version("PAID", 8)

print("STRICT PLACEMENT: preferred set = A,B,C")
write_acks = ["A", "B"]
for n in write_acks:
    replicas[n] = new
read_set = ["B", "C"]
print("W acknowledgements:", write_acks)
print("R responses:", [(n, replicas[n]) for n in read_set])
latest = max((replicas[n] for n in read_set), key=lambda v: v.version)
print("reconciled read:", latest)
print("R+W>N?", R + W > N, "intersection:", sorted(set(write_acks) & set(read_set)))

print("\nSLOPPY/SHIFTED PLACEMENT COUNTEREXAMPLE")
# A and B are unavailable during the write, so the write lands on C and fallback D.
replicas = {"A": Version("AUTHORIZED", 7), "B": Version("AUTHORIZED", 7),
            "C": Version("PAID", 8), "D": Version("PAID", 8)}
write_acks = ["C", "D"]
# Later A and B recover; a read that contacts A and B can satisfy R=2 but miss v8.
read_set = ["A", "B"]
print("W acknowledgements:", write_acks)
print("R responses:", [(n, replicas[n]) for n in read_set])
print("R+W>N?", R + W > N, "actual intersection:", sorted(set(write_acks) & set(read_set)))
print("read returns latest?", max(replicas[n].version for n in read_set) == 8)
print("lesson: arithmetic cannot guarantee overlap when membership/placement assumptions changed")

Verification checklist

• In the strict-placement case, the W and R sets share B.
• The reconciled read sees version 8 because one responder contains it and the simulator uses a monotonic version number.
• In the shifted-placement case, R+W>N remains numerically true but the actual sets are disjoint.
• The failure is diagnosed as an assumption failure, not an arithmetic error.
• You can name the version/reconciliation rule required after an overlap is found.

6. Production judgment

Quorum arithmetic is appropriate as a design tool when replica membership and operation semantics are explicit. It is dangerous as a label. Track coordinator timeouts, failed consistency-level requests, replica version divergence, hint queues, repair age, topology epochs, and per-key hot spots. Test partitions and membership changes in isolated environments. Do not infer security, tenant isolation, backup durability, or disaster recovery from an N/R/W tuple.

The next lesson keeps the same mechanics but varies the per-operation response requirement to show how tunable consistency moves latency, availability, and freshness risk.

Authoritative references

• Dynamo: Amazon’s Highly Available Key-value Store — primary reference for N/R/W, sloppy quorum, versions, hinted handoff, and Merkle-tree anti-entropy
• Apache Cassandra 5.0 — cqlsh consistency levels — current implementation example exposing ONE, QUORUM, ALL, LOCAL_ONE, LOCAL_QUORUM, and serial levels
• Herlihy & Wing — Linearizability — primary definition separating linearizable histories from quorum arithmetic