Replication and quorums
Read and write a majority of replicas so that every read overlaps the latest write.
from itertools import combinations
N = 3
replicas = [{"version": 0, "value": None} for _ in range(N)]
def write(value, version, targets):
for i in targets:
replicas[i] = {"version": version, "value": value}
def read(targets):
return max((replicas[i] for i in targets), key=lambda r: r["version"])["value"]
write("v1", 1, [0, 1])
print(read([1, 2]))
print(read([2]))
def always_overlap(w, r):
return all(set(ws) & set(rs) for ws in combinations(range(N), w) for rs in combinations(range(N), r))
print(always_overlap(2, 2))
print(always_overlap(2, 1))v1 None True False
Explanation
To survive machine failures, distributed systems keep several copies, called replicas, of the same data. Replication brings consistency problems: if a write reaches only some replicas, readers may see stale data. A quorum system controls this by requiring a write to be acknowledged by W of the N replicas and a read to consult R replicas.
If R + W > N, every read set and every write set must share at least one replica, because together they would otherwise need more than N distinct nodes. A reader that takes the value with the newest version among the replicas it asks is therefore guaranteed to see at least one copy of the latest completed write. Dynamo-style stores use this idea with tunable R and W. With N = 3, choosing W = 2 and R = 2 satisfies R + W > N and still tolerates one failed replica for both reads and writes.
The example keeps three replicas, writes version 1 to two of them, and reads from two others. The read overlaps the write at replica 1 and returns the new value. Reading only replica 2 returns the stale None. The final lines test every combination of read and write sets exhaustively: overlap holds with R = 2, W = 2, and fails with R = 1. Overlap alone is not full linearizability, and the CAP theorem reminds us that during a network partition a system must give up either consistency or availability.
Explore the dry run
from itertools import combinations N = 3replicas = [{"version": 0, "value": None} for _ in range(N)] def write(value, version, targets): for i in targets: replicas[i] = {"version": version, "value": value} def read(targets): return max((replicas[i] for i in targets), key=lambda r: r["version"])["value"] write("v1", 1, [0, 1])print(read([1, 2]))print(read([2])) def always_overlap(w, r): return all(set(ws) & set(rs) for ws in combinations(range(N), w) for rs in combinations(range(N), r)) print(always_overlap(2, 2))print(always_overlap(2, 1))Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| A write to two of three replicas (W = 2): replica 2 has not received it yet. | replicas: v1, v1, none | — | |
| A read of two replicas includes replica 1, which has version 1, so the newest version is returned. | replicas: v1, v1, none | v1 | |
| Reading only the stale replica returns None: with R = 1 the read missed the write. | replicas: v1, v1, none | v1 None | |
| Every possible pair of write replicas and pair of read replicas intersect, since 2 + 2 > 3. | replicas: v1, v1, none | v1 None True | |
| With R = 1 some read sets miss the write set entirely, since 2 + 1 is not greater than 3. | replicas: v1, v1, none | v1 None True False |
Cost and common mistakes
A quorum operation contacts R or W replicas in parallel, so latency is that of the slowest replica in the quorum, while message count is O(R) or O(W).
- R + W > N guarantees overlap, not linearizable behavior. Concurrent writes, failures, and sloppy quorums need extra mechanisms such as read repair and versioning.
- Higher R and W give stronger consistency but lower availability and higher latency.
- Replica versions must be ordered correctly. Using unsynchronized wall-clock timestamps can pick the wrong winner.
Try it yourself
With N = 5, which (W, R) pairs guarantee overlap and tolerate two failed replicas for both reads and writes?
Reveal answer and reasoning
W = 3 and R = 3. They overlap since 3 + 3 > 5, and each quorum can still be formed from the 3 replicas that remain after two failures.