# Replication Strategies and Quorums — Distributed Systems & Consensus (Raft / Paxos)

Source: https://www.skillbyai.com/en/distributed-consensus/dc-replication

> Compare single-leader, multi-leader and leaderless replication and reason about quorum overlap.

## Three ways to keep copies

**Replication** keeps copies of the same data on several nodes. In **single-leader** replication, all writes go to one leader that streams changes to followers; it gives a clear order of writes but the leader is a bottleneck and must be replaced on failure, which is exactly where consensus comes in. **Multi-leader** replication accepts writes at several leaders (often one per data centre) and syncs them asynchronously, so concurrent writes conflict and need resolution. **Leaderless** replication (Dynamo-style, as in Cassandra) lets clients write to several replicas directly and uses **quorums**: with N replicas, a write waits for W acknowledgements and a read queries R replicas. If **W + R > N**, every read set overlaps every write set in at least one node, so a read can see the latest acknowledged write, though without consensus there are still edge cases (concurrent writes, sloppy quorums) where this is not linearizable.

## Replication topologies

Single-leader funnels writes through one node; multi-leader accepts writes in several places; leaderless sends writes and reads to overlapping quorums.

![Three stages: single-leader replication, multi-leader replication, and leaderless quorum replication.](assets/figures/distributed-consensus/section-3-map.svg) — Figure 3.1: single-leader -> multi-leader -> leaderless quorums

## Checking quorum overlap by brute force

Enumerate every possible write set and read set and check that they always intersect.

```python
from itertools import combinations

def always_overlap(n, w, r):
    nodes = range(n)
    return all(set(ws) & set(rs)
               for ws in combinations(nodes, w)
               for rs in combinations(nodes, r))

for n, w, r in [(3, 2, 2), (3, 1, 1), (5, 3, 3), (5, 2, 3), (5, 4, 2)]:
    print(f"N={n} W={w} R={r}  W+R>N: {w + r > n!s:5}  overlap: {always_overlap(n, w, r)}")
```

Output:

```
N=3 W=2 R=2  W+R>N: True   overlap: True
N=3 W=1 R=1  W+R>N: False  overlap: False
N=5 W=3 R=3  W+R>N: True   overlap: True
N=5 W=2 R=3  W+R>N: False  overlap: False
N=5 W=4 R=2  W+R>N: True   overlap: True
```

## Majority is a special quorum

Consensus protocols use **majority quorums** (more than N/2) for both phases. Any two majorities overlap, which is the single property Raft and Paxos lean on to make sure a new leader learns about every committed decision.

**Quiz:** With N = 5 replicas, which setting guarantees read and write quorums always overlap?

- [ ] W = 2, R = 2
- [ ] W = 1, R = 3
- [x] W = 3, R = 3
- [ ] W = 2, R = 3

*Answer:* W = 3, R = 3. Overlap needs W + R > N. Only 3 + 3 = 6 exceeds 5; the other combinations total 4 or 5.