CS Fundamentals Trainer · Guides

Consensus: Raft, leader election and log replication

How a group of machines agrees on a log despite crashes: quorums, Raft's terms, randomised elections, replication and the commit rule, partitions and what survives them, with a simulation, fault injection and two step-by-step animations.

29 min read

A single server is simple: it decides, and everyone else believes it. The moment you copy data to several servers to survive failures (see replication), you need an answer to a hard question: when the servers disagree or some of them cannot be reached, which answer is the truth? Consensus is the family of protocols that gets a group of machines to agree on a value, or a sequence of values, even when some of them crash and messages are delayed or lost. It is what sits underneath etcd (and so Kubernetes), ZooKeeper, Consul, and the metadata of many databases and queues.

This guide explains consensus through Raft, the protocol designed to be understandable, and shows it working. I wrote a small Raft simulation (election, log replication, crashes and partitions) and ran it thousands of times; the code is in the appendix.

Read this first: this is a simulation, not a production implementation. Everything measured below (election times, the 0-violation safety run) comes from a roughly 150-line Python model in simulated time. It deliberately leaves out what makes a real Raft deployment safe and usable: durable state (currentTerm, votedFor and the log must be flushed to disk before a node replies), snapshots and log compaction, membership changes, pre-vote and leadership transfer, safe linearizable reads, and real networks and disks (partial failures, slow disks, clock jumps). Section 5 lists these, and section 5.1 works through the membership change, because it is the one most often done wrongly. The numbers show how the protocol behaves; they say nothing about the speed or safety of any real system.

1. The problem: a replicated state machine

The standard way to build a fault-tolerant service is a replicated state machine: every node starts in the same state and applies the same commands in the same order. If the commands are deterministic, the states stay identical. Consensus is how the nodes agree on that log of commands.

Diagram: A replicated log feeds identical state machines

What a consensus protocol promises (the textbook names):

There is a well-known limit: the FLP result (Fischer, Lynch and Paterson, 1985) proves that in a fully asynchronous network, where a slow node cannot be told from a dead one, no deterministic protocol can guarantee that it always terminates if even one node may crash. Real protocols accept this: they always stay safe and make progress only when the network is reasonably timely (randomised timeouts in Raft are exactly how it gets around FLP in practice). That is the same trade as in the CAP guide: when it cannot reach a majority, a consensus system chooses consistency and stops answering instead of risking two answers.

2. Quorums: why a majority

The key idea is the quorum. A decision needs the agreement of a majority of the N nodes, that is, more than N/2. Any two majorities share at least one node, so a later majority always contains someone who knew about the earlier decision. That overlap is what stops two halves of a split cluster from deciding different things.

Nodes NMajorityFailures tolerated
321
431
532
743

Two consequences you should remember. An even number of nodes does not help: four nodes still tolerate only one failure, like three, and need a larger majority. And more nodes make writes slower, not faster: every write waits for a majority, so adding nodes adds replication work and tail latency. Production clusters usually have 3 or 5 members; more is for tolerating more simultaneous failures, not for scale.

3. Raft in one page

Raft splits the problem into leader election, log replication and safety. At any time each node is a follower, a candidate or the leader, and time is divided into numbered terms. There is at most one leader per term.

Diagram: The three roles of a Raft node

Leader election

When a follower's timer expires it increments its term, becomes a candidate, votes for itself and asks the others for votes. A node grants one vote per term, first come first served, and only if the candidate's log is at least as up to date as its own (compare the term of the last entry, then the length). A candidate with votes from a majority becomes the leader and starts sending heartbeats.

Step through an election after the leader crashes. Switch on the option to see a split vote:

Interactive animation: raft election

If two candidates split the votes, nobody wins, the timers run out again, and a new term starts. The reason the timers are random is to make that unlikely. I tested this in the simulation: five nodes, message delays of 5 to 15 ms, a heartbeat every 50 ms, and 500 runs for each setting of the election timeout, measuring the time from the start until a first leader exists:

Election timeout rangeMedian to first leader99th percentileFailed elections per run
150 to 300 ms (a spread of 150 ms)188 ms356 ms0.37
150 to 160 ms (almost the same)1,126 ms5,926 ms16.1
1,000 to 2,000 ms (long)1,145 ms1,582 ms0.05

A wide enough random range makes elections quick and rare to repeat. A range that is too narrow makes nodes time out together and split the vote over and over (16 failed elections per run on average, and almost 6 seconds at the 99th percentile). A range that is too long almost never splits, but the cluster is leaderless for a second or more every time it needs a new leader. The rule of thumb from the Raft paper: the timeout should be much larger than the broadcast time (so heartbeats arrive in time) and much smaller than the time between failures. Real implementations tune it to the network: for example 1 second inside a data centre, longer across regions.

When I crashed the leader of a five-node cluster 300 times, a new leader was known after a median of 195 ms and 540 ms at the 99th percentile, and none of the 300 committed writes was lost. During that time the cluster cannot accept writes: the failover pause is part of the design, and your clients need retries with backoff (see resilience patterns).

Log replication

The leader appends a client command to its log as a new entry (tagged with the current term), then sends it to the followers in AppendEntries messages. Each message names the entry that precedes the new ones (index and term); a follower accepts only if its own log has that entry (the log matching check) and otherwise refuses, and the leader backs up and sends earlier entries until the logs agree. An entry is committed once the leader has stored it on a majority. Only then does the leader apply it to its state machine and answer the client; followers learn the commit index from later messages and apply the entry too.

Interactive animation: raft replication

With all five nodes reachable, the entry is committed once the leader and two followers hold it. Switch on the option: with three nodes cut off, the leader reaches only one follower, 2 of 5 is not a majority, and the entry is never committed. The minority side must stop. If it carried on, two sides of a partition could each accept writes and the data would diverge.

Diagram: Replicating one write through a leader and two followers

Note the subtle rule in the commit step: a leader counts replicas to commit only entries from its own term. Entries from earlier terms become committed indirectly, when a later entry of the current term is committed after them. The Raft paper explains with a figure why committing an old-term entry by counting replicas alone could let it be overwritten later; implementations such as etcd have the leader append a no-op entry as soon as it is elected for this reason.

4. Why it is safe

Raft's safety rests on two rules that fit together.

  1. A candidate needs a majority of votes, and a voter refuses a candidate whose log is less up to date than its own.
  2. An entry is committed only after a majority stored it.

Because any two majorities overlap, every possible winner of a later election was in the majority that stored each committed entry, so it must hold that entry, so the "up to date" check lets it win only if it has them all. Committed entries are never lost, and the winner's log is the one every follower is brought into line with.

The partition experiment

I cut a five-node cluster into a minority of two (the old leader and one follower) and a majority of three, and sent a write to each side:

minority leader 0:  log [(term 1, a=1), (term 1, lost=1)]  commit index 1
majority leader 2:  log [(term 1, a=1), (term 2, b=2)]     commit index 2
after healing, node 0: log [(term 1, a=1), (term 2, b=2)]  role: follower

The old leader kept believing it was the leader and accepted lost=1, but could not reach a majority, so it never committed it and the client never got a success. The majority elected a new leader in term 2 and committed b=2. When the partition healed, the old leader saw the higher term, stepped down, and its uncommitted entry was overwritten with the majority's log. This is the correct outcome: the write that was not acknowledged disappears, and everything that was acknowledged is still there. The lesson for clients: a timeout or a lost connection on a write means "unknown", not "failed"; use idempotent commands or an idempotency key (see the limits of idempotency keys).

Fault injection

A single scenario proves little, so I let the simulation run randomly: 200 runs of 60 steps, each step a random mix of crashing a node (never below a majority alive), restarting one, cutting random links, healing, or proposing a command. After every step I checked two properties: at most one leader per term, and the committed prefixes of all nodes' logs agree. Result: 0 violations, with 4,917 entries committed in total. This is a test of a simplified implementation, not a proof, and the real protocol has been formally specified and checked (the Raft authors published a TLA+ specification, and Paxos and Raft have been verified in tools such as Verdi and Ivy); but it shows the kind of testing that distributed protocols need. Tools such as Jepsen exist to do this against real systems.

5. What my simulation leaves out

It is about 150 lines and keeps the heart of Raft. A real implementation also needs:

This is why you should not write your own consensus. Use a tested implementation (etcd's Raft library, HashiCorp Raft, ZooKeeper's ZAB, a managed service) and spend your effort on using it correctly.

5.1 A worked example: changing the membership with joint consensus

Adding or removing servers looks harmless and is one of the most dangerous operations in a cluster, because different nodes learn about a new configuration at different moments. If some nodes count votes with the old member list and others with the new one, two different majorities can exist at the same time, and with them two leaders in one term.

The failure. A cluster of three (S1, S2, S3) grows to five (S1 to S5) in one step. The configuration entry reaches S4 and S5 and S3 first; S1 and S2 are slow and still use the old list. Now S1 asks S2 for a vote and wins with 2 of 3, the majority of the old configuration. At the same moment S3 asks S4 and S5 and wins with 3 of 5, the majority of the new one. Two leaders, same term, and both can commit different entries. I checked this by brute force over every subset of nodes (script in the appendix): ['S1', 'S2'] and ['S3', 'S4', 'S5'] are majorities of the old and the new configuration with no node in common. Replacing {S1, S2, S3} by {S3, S4, S5} has the same problem (['S1', 'S2'] and ['S3', 'S4']).

Joint consensus (the method in the Raft paper) avoids it with an intermediate configuration, C(old,new), in which a decision needs a majority of the old members and a majority of the new members. For the replacement of {S1, S2, S3} by {S3, S4, S5}:

StepWhat the leader doesWho must agree to commit it
1Appends C(old,new) to its log and replicates it. Each node uses a configuration as soon as it appears in its log, committed or not.2 of {S1, S2, S3} and 2 of {S3, S4, S5}
2While C(old,new) is in effect, elections and entries also need both majorities. Neither old nor new alone can decide anything.both majorities
3Once C(old,new) is committed, appends C(new).2 of {S3, S4, S5}
4When C(new) is committed, the old members that are not in the new set (S1, S2) are no longer needed. A leader that is not in C(new) steps down after committing it.

The brute force confirms the property that matters: in the joint phase every possible quorum overlaps both the old-only and the new-only quorums, and also every other joint quorum (all 64 joint quorums, 4 old-only and 16 new-only for the three-to-five case, with no disjoint pair). At no moment can two leaders be elected on different configurations.

If the leader crashes in the middle: if C(old,new) had not reached a majority, the new leader never sees it and the change is simply lost (retry it). If it had been committed, any node that could win an election must hold it (the election rule requires an up-to-date log), so the new leader finishes the change by appending C(new). Both outcomes are safe because every decision always involves a majority of the old members until C(new) is committed.

Single-server changes are the simpler alternative that most implementations use today: add or remove one server at a time. A majority of N nodes and a majority of N+1 (or N-1) always share a node, so no joint phase is needed. The brute force checked every size from 1 to 8 in both directions and found no disjoint pair. The rule is therefore: never change more than one voting member per step, and wait for each change to be committed before starting the next. Going from three to five nodes is two changes, not one.

What the example does not cover: new servers should join first as non-voting learners and catch up (otherwise a slow new node can stall commits while it is counted), and a removed server that is not told can disturb the cluster with elections unless pre-vote or a check-quorum rule is used. These are the details that real libraries implement and that my simulation does not.

6. Where consensus fits, and where it does not

Consensus is slow and sensitive compared with ordinary replication: every decision costs a round trip to a majority and a disk flush, and the leader is a bottleneck. So it is used for small, critical data, the control plane, not for the bulk data plane:

For bulk replication a database often uses simpler, cheaper leader-based replication that is not consensus (the replication guide shows what an asynchronous follower can lose).

Fencing tokens: a lock is not enough

A common bug: client A takes a lock from a consensus-backed service, pauses (a long garbage-collection pause, a stall of the VM), the lock expires, client B takes it, then A wakes up and writes, believing it still holds the lock. The fix is a fencing token: the lock service hands out a number that increases with every grant, the client sends it with every write, and the storage refuses any token lower than one it has already seen. Consensus gives you a correct lock service; it cannot stop a paused client from acting on a stale belief, so the check must happen at the resource.

Raft, Paxos and the others

Paxos (Lamport) solves the same problem and came first; its basic form agrees on a single value, and Multi-Paxos repeats it for a log. It is harder to explain and to implement completely, which was the motivation for Raft. ZAB (ZooKeeper) and Viewstamped Replication are close relatives. All of these assume nodes crash and stop; they do not defend against nodes that lie or are compromised. Surviving that needs Byzantine fault tolerant protocols (PBFT and the protocols behind blockchains), which need 3f+1 nodes to tolerate f faulty ones and are much more expensive.

7. Common mistakes

8. Things to mention in an interview

Quick recap

Appendix: the experiment code

One Python 3 file with no dependencies. It simulates five nodes in simulated time (milliseconds) with random message delays, so each run is repeatable from its seed. It implements leader election with randomised timeouts, the up-to-date log rule, AppendEntries with the log matching check, the commit rule (only entries of the leader's own term are committed by counting replicas) and the overwriting of conflicting log suffixes. It does not implement persistence, snapshots, membership changes, pre-vote or reads, and its nodes never lose their state when they crash (a restarted node keeps its term, vote and log, which is what a real node must guarantee by writing to disk before replying). The numbers in the guide come from the __main__ section; they will be identical on your machine because everything is seeded.

A Raft simulation: elections, replication, partitions and fault injection

"""A small Raft simulation: leader election, log replication and failures, in simulated time (milliseconds)."""
import heapq, random, itertools

class Sim:
    def __init__(self, n=5, seed=0, timeout=(150, 300), delay=(5, 15), heartbeat=50):
        self.n, self.rnd, self.timeout, self.delay, self.hb = n, random.Random(seed), timeout, delay, heartbeat
        self.t = 0; self.q = []; self.seq = itertools.count()
        self.term = [0]*n; self.voted = [None]*n; self.role = ['follower']*n; self.log = [[] for _ in range(n)]  # entries: (term, command)
        self.commit = [0]*n; self.alive = [True]*n; self.deadline = [0]*n; self.votes = [set() for _ in range(n)]
        self.next = [[1]*n for _ in range(n)]; self.match = [[0]*n for _ in range(n)]
        self.cut = set()                       # pairs (a,b) that cannot talk
        self.leaders = {}                      # term -> set of leaders (safety check: at most one per term)
        self.elections = 0; self.first_leader_at = None; self.applied = [[] for _ in range(n)]
        for i in range(n): self.reset_timer(i)
        for i in range(n): self.at(self.deadline[i], ('tick', i))
    def at(self, when, ev): heapq.heappush(self.q, (when, next(self.seq), ev))
    def reset_timer(self, i): self.deadline[i] = self.t + self.rnd.uniform(*self.timeout)
    def send(self, a, b, msg):
        if (a, b) in self.cut or (b, a) in self.cut: return
        self.at(self.t + self.rnd.uniform(*self.delay), ('msg', b, a, msg))
    def last(self, i): return (self.log[i][-1][0] if self.log[i] else 0, len(self.log[i]))
    def become_follower(self, i, term):
        if term > self.term[i]: self.term[i] = term; self.voted[i] = None
        self.role[i] = 'follower'
    def start_election(self, i):
        self.term[i] += 1; self.role[i] = 'candidate'; self.voted[i] = i; self.votes[i] = {i}; self.elections += 1
        self.reset_timer(i)
        for j in range(self.n):
            if j != i: self.send(i, j, ('vote?', self.term[i], self.last(i)))
    def become_leader(self, i):
        self.role[i] = 'leader'; self.leaders.setdefault(self.term[i], set()).add(i)
        if self.first_leader_at is None: self.first_leader_at = self.t
        self.next[i] = [len(self.log[i]) + 1]*self.n; self.match[i] = [0]*self.n; self.match[i][i] = len(self.log[i])
        self.broadcast(i)
    def broadcast(self, i):
        if not self.alive[i] or self.role[i] != 'leader': return
        for j in range(self.n):
            if j == i: continue
            prev = self.next[i][j] - 1; pt = self.log[i][prev-1][0] if prev else 0
            self.send(i, j, ('append', self.term[i], prev, pt, self.log[i][prev:], self.commit[i]))
        self.at(self.t + self.hb, ('beat', i, self.term[i]))
    def propose(self, cmd):
        for i in range(self.n):
            if self.alive[i] and self.role[i] == 'leader':
                self.log[i].append((self.term[i], cmd)); self.match[i][i] = len(self.log[i]); return i
    def advance_commit(self, i):
        for idx in range(len(self.log[i]), self.commit[i], -1):
            if self.log[i][idx-1][0] == self.term[i] and sum(m >= idx for m in self.match[i]) > self.n // 2:
                self.commit[i] = idx; break
    def handle(self, i, src, msg):
        kind = msg[0]
        if kind in ('vote?', 'append') and msg[1] > self.term[i]: self.become_follower(i, msg[1])
        if kind == 'vote?':
            _, term, (lt, ll) = msg
            ok = term == self.term[i] and self.voted[i] in (None, src) and (lt, ll) >= self.last(i)   # candidate's log at least as up to date
            if ok: self.voted[i] = src; self.reset_timer(i)
            self.send(i, src, ('vote', self.term[i], ok))
        elif kind == 'vote':
            _, term, ok = msg
            if term > self.term[i]: self.become_follower(i, term)
            elif self.role[i] == 'candidate' and term == self.term[i] and ok:
                self.votes[i].add(src)
                if len(self.votes[i]) > self.n // 2: self.become_leader(i)
        elif kind == 'append':
            _, term, prev, pt, entries, lc = msg
            if term < self.term[i]: self.send(i, src, ('ack', self.term[i], False, 0)); return
            self.role[i] = 'follower' if self.role[i] != 'leader' else self.role[i]; self.reset_timer(i)
            if prev > len(self.log[i]) or (prev and self.log[i][prev-1][0] != pt): self.send(i, src, ('ack', self.term[i], False, prev)); return
            self.log[i] = self.log[i][:prev] + list(entries)           # overwrite any conflicting suffix
            self.commit[i] = max(self.commit[i], min(lc, len(self.log[i])))
            self.send(i, src, ('ack', self.term[i], True, prev + len(entries)))
        elif kind == 'ack':
            _, term, ok, idx = msg
            if term > self.term[i]: self.become_follower(i, term); return
            if self.role[i] != 'leader' or term != self.term[i]: return
            if ok: self.match[i][src] = max(self.match[i][src], idx); self.next[i][src] = self.match[i][src] + 1; self.advance_commit(i)
            else: self.next[i][src] = max(1, self.next[i][src] - 1)
    def run(self, until):
        while self.q and self.q[0][0] <= until:
            when, _, ev = heapq.heappop(self.q); self.t = when
            if ev[0] == 'tick':
                i = ev[1]
                if self.alive[i]:
                    if self.role[i] != 'leader' and self.t >= self.deadline[i]: self.start_election(i)
                self.at(self.t + 10, ('tick', i))
            elif ev[0] == 'beat':
                _, i, term = ev
                if self.alive[i] and self.role[i] == 'leader' and self.term[i] == term: self.broadcast(i)
            elif ev[0] == 'msg':
                _, dst, src, msg = ev
                if self.alive[dst]: self.handle(dst, src, msg)
        self.t = until
    def leader(self):
        ls = [i for i in range(self.n) if self.alive[i] and self.role[i] == 'leader']
        return max(ls, key=lambda i: self.term[i]) if ls else None
    def crash(self, i): self.alive[i] = False; self.role[i] = 'follower'
    def restart(self, i): self.alive[i] = True; self.role[i] = 'follower'; self.reset_timer(i)

def safety(s):
    one_leader_per_term = all(len(v) <= 1 for v in s.leaders.values())
    # committed prefixes must agree on every node
    ok = True
    for a in range(s.n):
        for b in range(s.n):
            k = min(s.commit[a], s.commit[b])
            if s.log[a][:k] != s.log[b][:k]: ok = False
    return one_leader_per_term, ok

if __name__ == "__main__":
    # 1. time to elect a leader from a cold start, by election timeout range
    for rng in ((150, 300), (150, 160), (1000, 2000)):
        ts = []; splits = 0
        for seed in range(500):
            s = Sim(seed=seed, timeout=rng); s.run(6000); ts.append(s.first_leader_at); splits += s.elections > 1 and s.first_leader_at is not None and (s.elections - 1)
        ts = sorted(t for t in ts if t is not None)
        print(f"timeout {rng}: median first leader {ts[len(ts)//2]:.0f} ms, 99th percentile {ts[int(len(ts)*.99)]:.0f} ms, worst {ts[-1]:.0f} ms, failed elections before the first leader, per run {splits/500:.2f}")
    # 2. crash the leader: how long until a new leader is known, and does a committed write survive?
    outage = []; lost = 0
    for seed in range(300):
        s = Sim(seed=seed); s.run(1000); l = s.leader(); s.propose("x=1"); s.run(1300)
        assert s.commit[l] == 1                     # the write is committed on the leader
        s.crash(l); t0 = s.t
        while s.leader() is None and s.t < t0 + 5000: s.run(s.t + 5)
        outage.append(s.t - t0); s.run(s.t + 1000)
        nl = s.leader(); lost += nl is None or s.log[nl][:1] != [(s.log[nl][0][0], "x=1")]
        assert all(safety(s))
    outage.sort(); print(f"leader crash: new leader after median {outage[150]:.0f} ms, 99th percentile {outage[297]:.0f} ms; committed writes lost: {lost} of 300")
    # 3. a partition: the minority side cannot commit, the majority can, and after healing the minority's entries are overwritten
    s = Sim(seed=3); s.run(1000); old = s.leader(); s.propose("a=1"); s.run(1200)
    minority = {old, (old + 1) % 5}; majority = set(range(5)) - minority
    for a in minority:
        for b in majority: s.cut.add((a, b))
    s.propose("lost=1"); s.run(1800)                # the old leader accepts a write it can only reach one follower with
    print("minority leader", old, "log", s.log[old], "commit", s.commit[old])
    for _ in range(200):
        l = max((i for i in majority if s.role[i] == 'leader'), key=lambda i: s.term[i], default=None)
        if l is not None: break
        s.run(s.t + 20)
    l = max((i for i in majority if s.role[i] == 'leader'), key=lambda i: s.term[i]); s.log[l].append((s.term[l], "b=2")); s.match[l][l] = len(s.log[l]); s.run(s.t + 600)
    print("majority leader", l, "log", s.log[l], "commit", s.commit[l])
    s.cut.clear(); s.run(s.t + 1500)
    print("after healing: old leader's log", s.log[old], "role", s.role[old], "term", s.term[old], safety(s))
    # 4. fault injection: random crashes, partitions and writes; check the two safety properties all along
    bad = 0; committed_total = 0
    for seed in range(200):
        s = Sim(seed=1000 + seed); rnd = random.Random(seed); k = 0
        for step in range(60):
            s.run(s.t + rnd.uniform(20, 200))
            r = rnd.random()
            if r < .15:
                v = rnd.randrange(5)
                if sum(s.alive) > 3 and s.alive[v]: s.crash(v)
            elif r < .3:
                for v in range(5):
                    if not s.alive[v]: s.restart(v); break
            elif r < .4: s.cut = {(a, b) for a in range(5) for b in range(5) if a < b and rnd.random() < .4}
            elif r < .5: s.cut = set()
            else: k += 1; s.propose(f"c{k}")
            if not all(safety(s)): bad += 1
        committed_total += max(s.commit)
    print(f"fault injection: 200 runs x 60 steps, safety violations: {bad}, entries committed in total: {committed_total}")
    # 5. quorum arithmetic
    for n in (3, 5, 7): print(f"{n} nodes: majority {n//2+1}, tolerates {n - (n//2+1)} failures")

Why membership changes need care: a brute-force check of quorum overlap

Runs in a fraction of a second with the standard library. It enumerates every majority for the old, new and joint configurations and looks for two that share no node.

"""Why a cluster cannot switch configuration in one step, and how joint consensus and
single-server changes avoid the problem. Brute force over all subsets of nodes."""
from itertools import combinations

def majorities(cfg):
    need = len(cfg) // 2 + 1
    return [set(c) for k in range(need, len(cfg) + 1) for c in combinations(sorted(cfg), k)]

def disjoint_pair(qs_a, qs_b):
    for a in qs_a:
        for b in qs_b:
            if not (a & b):
                return sorted(a), sorted(b)
    return None

def report(title, qa, qb):
    r = disjoint_pair(qa, qb)
    print(f"{title}: {'DISJOINT quorums exist, e.g. ' + str(r[0]) + ' and ' + str(r[1]) if r else 'every pair of quorums overlaps'}")

old = {"S1", "S2", "S3"}
new = {"S1", "S2", "S3", "S4", "S5"}
# 1. direct switch: some nodes still use the old configuration, others already the new one
report("direct switch 3 -> 5 nodes (old config vs new config)", majorities(old), majorities(new))

# 2. joint consensus: during C_old,new a decision needs a majority of C_old AND a majority of C_new
joint = [a | b for a in majorities(old) for b in majorities(new)]
report("joint phase vs old config alone", joint, majorities(old))
report("joint phase vs new config alone", joint, majorities(new))
report("joint phase vs joint phase", joint, joint)

# 3. replacing 3 nodes by 3 other nodes
old2, new2 = {"S1", "S2", "S3"}, {"S3", "S4", "S5"}
report("direct switch {S1,S2,S3} -> {S3,S4,S5}", majorities(old2), majorities(new2))
joint2 = [a | b for a in majorities(old2) for b in majorities(new2)]
report("joint {S1,S2,S3}+{S3,S4,S5} vs old alone", joint2, majorities(old2))
report("joint {S1,S2,S3}+{S3,S4,S5} vs new alone", joint2, majorities(new2))

# 4. single-server changes (one node added or removed at a time)
for n in range(1, 8):
    a = {f"S{i}" for i in range(n)}
    bigger = a | {f"S{n}"}
    r1 = disjoint_pair(majorities(a), majorities(bigger))
    print(f"single-server change {n} -> {n+1} nodes: {'DISJOINT' if r1 else 'overlap'}", end=" | ")
    if n > 1:
        smaller = set(sorted(a)[:-1])
        r2 = disjoint_pair(majorities(a), majorities(smaller))
        print(f"{n} -> {n-1}: {'DISJOINT' if r2 else 'overlap'}")
    else:
        print()
# 5. two changes at once (3 -> 5) is exactly the unsafe case from step 1
print("sizes of quorum sets: old", len(majorities(old)), "new", len(majorities(new)), "joint", len(joint))

Sources

Practise this topic: System Design System Design › Distributed systems

More guides