Why does W + R > N guarantee overlap, exactly?

Because two subsets of a set of N items, sized W and R, must share at least one element whenever W + R > N -- if they didn't overlap at all, they'd together need W + R distinct items, which is more than the N that exist. It's a pigeonhole argument, not a property specific to databases.

If W=1, R=1 is unsafe, why would anyone use it?

Speed and availability -- a write only needs one replica to ack (fast, tolerates N-1 replicas being down) and a read only needs one replica to answer (same). Systems that choose this tradeoff (many NoSQL defaults) are explicitly choosing eventual consistency over the guarantee this lesson demonstrates, usually because the workload can tolerate briefly stale reads.

Does a strong quorum (W+R>N) guarantee the read returns the single latest write, or just *a* recent one?

In this simplified model, exactly the latest one -- `read` takes the max version seen across the quorum, and the overlap guarantee ensures at least one queried replica has that latest version. Real systems add extra machinery (vector clocks, read-repair) to handle write ordering and conflicting concurrent writes, which this lesson doesn't model.

What does 'exactly-once' distributed systems documentation usually mean if not this?

It almost always means exactly-once *effects*, achieved through idempotency keys and deduplication (see the events-vs-commands and idempotent-consumers lessons in the event-driven topic), not a literal guarantee that a message is delivered exactly one time at the network level -- that guarantee doesn't exist over an unreliable network.

Quorum Consistency: When a Read Is Guaranteed to See the Latest Write

A quorum read only sees the latest write for certain if it’s mathematically impossible for the read and write sets to miss each other entirely.

Strong quorum sees the write; weak quorum can miss it

class ReplicaSet:
    def __init__(self, num_replicas):
        self.replicas = [0] * num_replicas  # each replica stores a "version" of the data

    def write(self, write_quorum, new_version, replica_order):
        acked = replica_order[:write_quorum]
        for r in acked:
            self.replicas[r] = new_version
        return acked

    def read(self, read_quorum, replica_order):
        queried = replica_order[:read_quorum]
        versions = [self.replicas[r] for r in queried]
        return queried, max(versions)

replicas = ReplicaSet(num_replicas=5)

# Strong quorum: W=3, R=3, N=5 (W+R=6 > N, overlap guaranteed)
print("Strong quorum: W=3, R=3, N=5")
acked = replicas.write(write_quorum=3, new_version=1, replica_order=[0, 1, 2, 3, 4])
print(f"  write acked by replicas {acked}, replica state: {replicas.replicas}")
queried, version = replicas.read(read_quorum=3, replica_order=[2, 3, 4, 0, 1])
print(f"  read queried replicas {queried}, saw version {version} (latest is 1)")

# Weak quorum: W=1, R=1, N=5 (W+R=2 <= N, no overlap guaranteed)
replicas2 = ReplicaSet(num_replicas=5)
print()
print("Weak quorum: W=1, R=1, N=5")
acked = replicas2.write(write_quorum=1, new_version=1, replica_order=[0, 1, 2, 3, 4])
print(f"  write acked by replicas {acked}, replica state: {replicas2.replicas}")
queried, version = replicas2.read(read_quorum=1, replica_order=[3, 0, 1, 2, 4])
print(f"  read queried replicas {queried}, saw version {version} (latest is 1, but this read might miss it)")

$ python quorum_consistency.py
Strong quorum: W=3, R=3, N=5
  write acked by replicas [0, 1, 2], replica state: [1, 1, 1, 0, 0]
  read queried replicas [2, 3, 4], saw version 1 (latest is 1)

Weak quorum: W=1, R=1, N=5
  write acked by replicas [0], replica state: [1, 0, 0, 0, 0]
  read queried replicas [3], saw version 0 (latest is 1, but this read might miss it)

With W=3, R=3, N=5, the write set {0,1,2} and read set {2,3,4} are forced to share at least one replica — here, replica 2 — so the read sees version 1 no matter which 3 replicas it happens to query. With W=1, R=1, N=5, the write only reached replica 0, and this particular read happened to query replica 3 instead — a real, demonstrated stale read, not a hypothetical one.

Practice

1. Run the weak-quorum case again with a read that happens to query the replica that got the write.

class ReplicaSet:
    def __init__(self, num_replicas):
        self.replicas = [0] * num_replicas

    def write(self, write_quorum, new_version, replica_order):
        acked = replica_order[:write_quorum]
        for r in acked:
            self.replicas[r] = new_version
        return acked

    def read(self, read_quorum, replica_order):
        queried = replica_order[:read_quorum]
        versions = [self.replicas[r] for r in queried]
        return queried, max(versions)

replicas = ReplicaSet(num_replicas=5)
replicas.write(write_quorum=1, new_version=1, replica_order=[0, 1, 2, 3, 4])
print(f"replica state: {replicas.replicas}")

# This time the weak-quorum read happens to query replica 0, which DID get the write
queried, version = replicas.read(read_quorum=1, replica_order=[0, 1, 2, 3, 4])
print(f"read queried replicas {queried}, saw version {version} -- got lucky this time")

$ python weak_quorum_lucky.py
replica state: [1, 0, 0, 0, 0]
read queried replicas [0], saw version 1 -- got lucky this time

A weak quorum doesn’t guarantee a stale read on every attempt — it just doesn’t rule one out. This read happened to land on the one replica that mattered; the main example’s read didn’t.

2. Exhaustively check every possible write/read set pair for W=2, R=2, N=3 and confirm none miss each other.

from itertools import combinations

N = 3
W = 2
R = 2

replicas = list(range(N))
all_write_sets = list(combinations(replicas, W))
all_read_sets = list(combinations(replicas, R))

no_overlap_found = False
for write_set in all_write_sets:
    for read_set in all_read_sets:
        overlap = set(write_set) & set(read_set)
        if not overlap:
            no_overlap_found = True
            print(f"NO OVERLAP: write={write_set}, read={read_set}")

print(f"Checked {len(all_write_sets)} write sets x {len(all_read_sets)} read sets")
print(f"Every pair overlapped: {not no_overlap_found}")

$ python exhaustive_overlap_check.py
Checked 3 write sets x 3 read sets
Every pair overlapped: True

This isn’t a sampled test — it’s every possible combination of a 2-replica write set and a 2-replica read set out of 3 total replicas, and all 9 pairs overlap. That’s the pigeonhole argument made concrete instead of just asserted.

3. Run a sequence of 3 writes through different replica subsets and confirm strong quorum reads always see the latest version.

class ReplicaSet:
    def __init__(self, num_replicas):
        self.replicas = [0] * num_replicas

    def write(self, write_quorum, new_version, replica_order):
        acked = replica_order[:write_quorum]
        for r in acked:
            self.replicas[r] = new_version
        return acked

    def read(self, read_quorum, replica_order):
        queried = replica_order[:read_quorum]
        versions = [self.replicas[r] for r in queried]
        return queried, max(versions)

replicas = ReplicaSet(num_replicas=5)

for version, order in [(1, [0, 1, 2, 3, 4]), (2, [1, 2, 3, 4, 0]), (3, [4, 0, 1, 2, 3])]:
    replicas.write(write_quorum=3, new_version=version, replica_order=order)
    _, seen = replicas.read(read_quorum=3, replica_order=list(reversed(order)))
    print(f"After write v{version}: replica state {replicas.replicas}, quorum read saw v{seen}")

$ python sequential_writes.py
After write v1: replica state [1, 1, 1, 0, 0], quorum read saw v1
After write v2: replica state [1, 2, 2, 2, 0], quorum read saw v2
After write v3: replica state [3, 3, 2, 2, 3], quorum read saw v3

Even as each write lands on a different rotating subset of 3 replicas, a strong-quorum read right after it always reports the version that was just written — the guarantee holds across a whole sequence, not just a single write/read pair.

4. Write a helper that checks whether a given N/W/R combination is a strong quorum, and test it against several real configurations.

def is_strong_quorum(n, w, r):
    return w + r > n

configs = [
    (5, 3, 3),
    (5, 1, 1),
    (3, 2, 2),
    (3, 1, 1),
    (7, 4, 4),
]

for n, w, r in configs:
    guaranteed = is_strong_quorum(n, w, r)
    print(f"N={n}, W={w}, R={r}: W+R={w + r}, strong quorum? {guaranteed}")

$ python strong_quorum_checker.py
N=5, W=3, R=3: W+R=6, strong quorum? True
N=5, W=1, R=1: W+R=2, strong quorum? False
N=3, W=2, R=2: W+R=4, strong quorum? True
N=3, W=1, R=1: W+R=2, strong quorum? False
N=7, W=4, R=4: W+R=8, strong quorum? True

(3, 1, 1) and (5, 1, 1) both fail the check despite having different replica counts — the guarantee depends only on the relationship between W, R, and N, not on how large the cluster happens to be.

Strong quorum sees the write; weak quorum can miss it

Practice

Frequently Asked Questions