Membership Change Under Joint Consensus

Replacing a failed node in a three-node cluster should be an operation on the order of a minute. Doing it by editing a configuration file on each node and restarting them is an operation that can lose committed data. The two are not the same operation, and the difference is that the set of participants in a consensus protocol is itself a value the protocol must agree on. Changing it is a consensus problem, and solving it with an out-of-band mechanism reintroduces every failure the protocol was built to avoid.

The failure that in-place editing causes

Take a five-node configuration C_old = {A, B, C, D, E} and a new one C_new = {A, B, C, D, F} that swaps E for F. An operator applies the change by rewriting the configuration on each node. The rewrites do not happen atomically, so there is a window in which some nodes use C_old and some use C_new.

Now suppose the leader is E, the node being removed, and it has not yet learned about the change. E counts acknowledgements against C_old and needs three of five. Nodes A and B have moved to C_new and count against C_new, needing three of five as well, but a different three. A write could be acknowledged by {E, D, C} under the old configuration and by {A, B, F} under the new one, with no overlap at all. Both sides believe they have a majority. Both commit. The two committed logs differ, and there is no rule that reconciles them, because each side’s commit was valid under the configuration it was using.

This is not a hypothetical race that requires adversarial timing. Any configuration change applied by a mechanism outside the log has this window, and the window lasts as long as it takes for the last node to receive the new configuration. The fix is not to make the window shorter; it is to make the protocol correct throughout the window.

Joint consensus: requiring both majorities

The joint-consensus approach introduces an intermediate configuration, written C_old,new, in which decisions require a majority of C_old and a majority of C_new. The transition is three steps, and every step is an entry in the replicated log rather than a change to local state.

The leader appends an entry that specifies C_old,new. From the moment that entry is committed, every decision, including elections, commits, and reads that require quorum confirmation, needs both majorities. The leader then appends an entry specifying C_new. Once that entry is committed, the cluster operates under C_new alone.

The dual-majority requirement is what closes the window. During the transition, a write is committed only if it reaches a majority of C_old and a majority of C_new, so no subset can commit under one configuration while another subset commits under the other. A node that has not yet learned about the transition still counts under C_old only, but it cannot commit anything on its own: it needs a majority of C_old, and any majority of C_old intersects the dual-majority quorum that the transitioned nodes are using, so at least one transitioned node must participate, and that node will refuse to count the write as committed until the C_new majority is also satisfied.

The cost is availability. During C_old,new, the cluster needs both majorities simultaneously, so it tolerates failures only up to the smaller of the two fault budgets. If C_old is three nodes and C_new is nine, the joint configuration behaves like a three-node cluster for availability purposes, and a single failure in the old set can stall the transition. This is why large membership changes are done in increments rather than all at once.

Elections during a transition

The election rules must also be dual-majority aware. A candidate in C_old,new must collect votes from a majority of C_old and a majority of C_new before it can become leader. A candidate that collects a majority of C_new but not of C_old is not leader, and must not act as one.

This is where implementations that bolt joint consensus onto a simple vote counter go wrong. A vote counter that sums votes and compares the total to n/2 + 1 for the union of the two configurations can declare a winner that has a majority of neither. The counting must be per configuration, and the two counts must be tracked separately.

There is a related subtlety about which configuration a node uses to decide whether a vote request is valid. A node that has not yet received the C_old,new entry uses C_old and considers itself a voter; a node that has received it uses the joint configuration. A candidate that has received the joint entry but is asking a node that has not is in the reverse situation. The rule that resolves this is that the configuration in effect for a node is the last configuration entry in its log, whether or not that entry is committed. Using the committed configuration instead would leave a node voting under an old configuration while the leader is operating under a new one.

Single-server changes and the safety margin

The alternative to joint consensus is to allow only one server to be added or removed at a time, and to treat the change as an ordinary log entry that takes effect immediately on append rather than on commit. This is the approach Raft’s dissertation analyses in detail and the one many implementations use, because it avoids the dual-majority machinery.

The safety argument for single-server changes rests on the overlap between the old and new majorities being large. Adding one server to a set of n changes the majority size from floor(n/2) + 1 to floor((n+1)/2) + 1, and the two quorum systems overlap in enough nodes that a decision under one cannot conflict with a decision under the other. Removing one server is symmetric. The argument fails when two changes are in flight simultaneously, which is why the rule is one at a time and why an implementation must reject a second configuration change while one is uncommitted.

The failure mode this permits is narrow but real. A leader that appends a configuration change and then crashes before the change is committed leaves the cluster in a state where some nodes have the new configuration and some do not. A new leader must determine which configuration is authoritative, and the rule it uses, namely the latest configuration in its log, can differ from the rule a follower uses. The single-server-change approach relies on the overlap being large enough that any leader elected under either configuration has a log consistent with the other, which holds for one change at a time and does not hold for two.

Adding a node without disrupting the quorum

A new node joins with an empty log. If it is added to the configuration before it has caught up, it counts toward the majority while holding none of the data, which effectively reduces the fault tolerance of the cluster by one for the duration of the catch-up.

The standard procedure is to add the node as a non-voting member first, replicate the existing log to it until it is close to caught up, and only then promote it to a voting member through the configuration change mechanism. Non-voting members receive entries and can serve as learners, but their acknowledgements do not count toward quorums. The promotion is then a single-server change from the protocol’s perspective, with the new node already holding a log that makes it a useful voter.

Removing a node has the mirror-image hazard: a removed node that has not been told it was removed continues to believe it is a voter and may start elections with ever-increasing terms, disrupting the cluster. The node must be shut down, or it must learn of its removal through the log and refuse to campaign. Implementations that remove a node by simply stopping it and editing the configuration leave the node’s process alive and campaigning, which is why removal should be done through the same log mechanism as addition.

What happens when the transition itself is interrupted

A joint-consensus transition that is interrupted by a leader failure resumes under the new leader, because the C_old,new entry is in the log and the new leader inherits it. The new leader operates under the joint configuration and can complete the transition by appending C_new. If the new leader’s log does not contain the joint entry, it operates under C_old, and the transition has not started from its perspective.

The dangerous case is a leader that crashes after appending C_new but before it is committed. The cluster is in C_old,new from the perspective of every node that has the entry, and the C_new entry is uncommitted. A new leader must not treat the uncommitted C_new as authoritative, and must instead continue operating under the joint configuration until it can commit C_new itself. An implementation that uses the last configuration entry in the log regardless of commit status can end up operating under C_new while the joint configuration’s dual-majority requirement is still needed to make the transition safe.

The resolution is that the configuration in effect for counting purposes is the last configuration entry in the log, but the transition from joint to final is only complete when the final entry is committed. Those two statements are compatible: a node uses C_new for counting once it has the entry, and the cluster as a whole has not left the joint state until a quorum has the entry committed.

Why this is not an operational detail

The temptation to treat membership as configuration rather than as replicated state comes from the fact that the initial membership has to be configured somehow, before any log exists. That bootstrap case is genuinely outside the protocol: the initial configuration is given, and every subsequent change is inside it.

Everything after bootstrap belongs in the log, and the reason is the same reason the log exists at all. A configuration change is a decision about which set of machines will make future decisions, and any decision that different nodes can disagree about is exactly what a consensus protocol is for. An out-of-band change is a decision made without consensus, and the failure it causes, two disjoint majorities both believing they are authoritative, is indistinguishable from the split brain the protocol was designed to prevent.

The interaction with quorum arithmetic is direct: quorums are counted against a configuration, and a cluster with two configurations has two quorum systems that need not intersect. Joint consensus is the construction that makes them intersect by requiring both at once, and single-server change is the construction that makes the overlap large enough that the intersection is automatic. Both are ways of ensuring that the answer to “which configuration is authoritative” is decided by the protocol rather than by the order in which operators edited files.

The other interaction worth noting is with log compaction. A configuration entry can be compacted away, and a node that joins later and receives a snapshot has no configuration entries in its log at all. The snapshot must therefore carry the configuration in effect at its last-included index, or the new node will not know which quorum to count against.