Membership Changes

You will eventually resize a live cluster — replace a dead machine, grow 3 → 5. The tempting implementation is a config-file flip plus rolling restart. It can end in two leaders.

The disjoint-majorities disaster

Grow {A, B, C} to {A, B, C, D, E}. Configuration cannot reach every node at the same instant, so there is a window where A and B still run the old config while C, D, E run the new one. Let elections fire inside that window:

A campaigns: votes {A, B}     = majority of C_old (2 of 3)  -> leader
D campaigns: votes {C, D, E}  = majority of C_new (3 of 5)  -> leader

Disjoint vote sets, both legitimate under "their" configuration, same time window: two leaders, diverging logs, committed-data loss — the exact split-brain Raft exists to prevent, self-inflicted by an ops change. Any safe scheme must make old-style and new-style majorities always overlap during the transition.

Joint consensus (§6)

Configuration changes travel through the log itself:

1. The leader appends a joint entry C_old,new. From that moment, every decision — elections and commits alike — needs a majority of C_old and a majority of C_new, counted independently.
2. Once C_old,new commits (under both majorities), the leader appends C_new.
3. Once C_new commits, the transition is done; members not in C_new shut down.

The subtlety implementations get wrong: a configuration takes effect the moment it is appended to a node's log — not when it commits. A server always uses the newest config entry it holds, committed or not. Waiting for commit would re-open the unsafe window the joint entry exists to close. Your exercise encodes this: the joint rule applies as soon as the change is proposed.

Why the overlap argument works: while any node might still decide under C_old, every joint-phase decision also demanded a C_old majority — those overlap. Decisions under C_new alone become possible only after C_old,new committed in C_new too — and C_new majorities overlap each other. At no instant can two disjoint sets both decide.

The simpler modern route

Ongaro's thesis showed that changing one server at a time never creates disjoint majorities — when configs differ by a single member, any majority of one intersects any majority of the other. So etcd and Consul skip joint consensus and serialize single-node changes (etcdctl member add is one node per operation). One published correction (2015): a freshly elected leader must first commit an entry of its own term before appending a config change.

The operational traps that remain: a newly added empty node raises quorum immediately — grow 3 → 4 and you need 3 healthy voters while the newcomer spends hours catching up. Add it as a non-voting learner first (etcd's learner mode) and promote it once caught up. And servers removed from the config may never get the memo, time out, and campaign with inflated terms — which is why servers ignore RequestVote received within a minimum election timeout of hearing from a live leader.

Your exercise

Implement joint-consensus majority checks. The grader-caught mistake: after INIT n1,n2,n3 and ADD n4, MAJORITY n1,n2 must print NO — 2 of 3 satisfies C_old, but 2 of 4 fails C_new, and the joint rule is already in force at the proposal, before any commit. After COMMIT_NEW the cluster is plainly {n1..n4}: MAJORITY n1,n4 prints NO (2 of 4) while MAJORITY n1,n2,n4 prints YES (3 of 4).