Why Fixed Membership Is Crucial for Paxos and How to Handle Dynamic Changes

The Essence of Majority

Before discussing member changes, we review the first article on Paxos theory, which defined the set of voters Bqrm needed for a successful vote. The second Paxos constraint requires any two Bqrm sets to intersect, meaning Bqrm essentially represents a majority within a fixed voter set.

All theoretical discussions assume a fixed voter set. When the voter set changes, the definition of Bqrm no longer corresponds to a majority, making it difficult to define and breaking Paxos consistency. Thus, fixed members are the foundation of Paxos.

Manual Configuration for Member Changes?

Reviewing the second article on Multi‑Paxos and leaders, we see that Paxos progresses via independent instances, each producing an ordered series. Within the same instance, all members must agree on the member set, so members remain fixed throughout a complete Paxos execution.

Members learn the set through configuration files. However, configuration changes may occur at any point between instances, potentially violating the requirement that all nodes share the same Bqrm. An illustration shows replacing node C with D, leading to conflicting Bqrm sets (A,C) and (B,D) with no intersection, thus breaking the Paxos protocol.

Note: Green indicates instances that have already learned the chosen value.

This demonstrates that without an atomic configuration switch, Paxos cannot guarantee consistency during member changes.

Side note: Manual configuration updates can be approximated with tools and careful observation, but they cannot achieve the theoretical guarantees required by Paxos. The upcoming dynamic member change algorithm addresses this.

Paxos Dynamic Member Change Algorithm

The algorithm is briefly mentioned in the final paragraph of "Paxos Made Simple". Multi‑Paxos produces an ordered series used as state‑machine inputs; the member set itself can be treated as state and updated via Paxos, ensuring all machines obtain a consistent member view.

In instance 4, the Paxos algorithm decides a member change from A,B,C to A,B,D, achieving atomic change across all nodes.

Delaying Change Effectiveness

In practice, Paxos is often engineered with a leader handling writes for performance. Member changes may cause leader turnover, leading to a surge of failed requests at the moment of change.

If multiple instances are submitted in parallel (windowed sliding), instances after a chosen member change may already have their Bqrm fixed, preventing further modification. To avoid this, we can delay the effective time of the member change, directing requests to the new leader only after the delay.

Define a delay window "a" and a change point "I"; the effective point becomes I + a. The old leader continues writing until I + a, after which the new leader takes over, enabling a smooth transition.

If the old leader stops writing after the change and the new leader must wait until I + a, the system can stall. In such cases, the new leader should write a null value during the gap (I, I + a) to fill the hole and keep the algorithm progressing.