Paxos Algorithm Overview and the Two‑Phase Paxos Member‑Group Change Method

This article, originally published on the InfoQ "Efficient Development & Operations" channel, provides a theoretical discussion of the Paxos consensus algorithm and a novel two‑phase Paxos member‑group change method.

1. Paxos Algorithm Introduction Paxos, proposed by Leslie Lamport, solves consistency in message‑passing distributed systems where processes may crash, restart, and messages can be delayed, lost, or duplicated. It defines three roles: proposer, acceptor, and learner. Proposers issue proposals (number n and value), acceptors decide to accept or reject, and learners learn the chosen value. Paxos guarantees correctness through two constraints: (1) liveness – eventually a proposal is chosen; (2) safety – acceptors can only choose proposals from proposers, only one value can be chosen per instance, and learners only learn the chosen value.

The algorithm proceeds in two phases: phase1a – proposer sends a prepare with number N; phase1b – acceptors respond with the highest accepted value for N (if any) and promise not to accept lower numbers; phase2a – proposer, after receiving a majority of promises, sends an accept with value V and number N; phase2b – acceptors accept the proposal if they have not promised a higher number. A single Paxos instance selects exactly one value.

2. Paxos Member‑Group Reconfiguration In practice, cluster members may fail or be replaced, requiring configuration changes. Simple approaches such as stopping the cluster to update all members break service availability, while naïvely treating the member list as a Paxos value can violate safety, leading to two concurrent majorities (as illustrated by a failed example image).

3. Baishan’s Proprietary Two‑Phase Paxos Member‑Group Change Algorithm The method imposes three constraints: (1) the cluster continues to serve reads/writes during reconfiguration; (2) no split‑brain (multiple leaders) may occur; (3) any interruption can resume without violating safety. The algorithm performs two consecutive Paxos instances: the first changes the old configuration C‑old to an intermediate state C‑old‑new (the union of old and new members); the second changes C‑old‑new to the final configuration C‑new. Each Paxos instance is identified by a monotonically increasing version, and only proposals with a version greater than the current one may be committed. Detailed steps, including proposal numbers, versions, and commit phases, are described with accompanying diagrams.

By ensuring that at any moment only one quorum (either old or new) can be formed, the algorithm avoids the split‑brain scenario. It also handles total cluster crashes: if no acceptor has accepted the proposal before the crash, the cluster continues with the old configuration; if a majority has accepted, the new configuration takes effect, satisfying all three constraints.

4. Application in Baishan Cloud Storage (CWN‑X) The storage system encodes a group of files into N data blocks and M parity blocks (EC algorithm) distributed across different disks (members). Using Paxos guarantees consistent member information across the cluster. The two‑phase Paxos reconfiguration enables simultaneous replacement of multiple members while preserving data safety, improving efficiency compared to single‑member change algorithms and supporting millions of EC clusters in production.

The article concludes with a brief author bio: Wu Yipu, senior R&D engineer at Baishan, known for high‑availability work on large‑scale storage systems.