How Paxos Guarantees Consistent Data Across Distributed Nodes

Paxos is a renowned distributed consensus algorithm, praised by Mike Burrows, the author of Google Chubby, who said, "There is only one consistency algorithm in this world, Paxos." Algorithms such as Raft and Zab are simplifications and improvements based on Paxos.

What Problem Does Paxos Solve

Paxos addresses data consistency among multiple nodes in a distributed environment. For example, in a three‑node cache cluster where each node can write, without a consensus algorithm the order of writes can become inconsistent, leading to divergent data states.

Node 1 may send updates to nodes 2 and 3; node 2 receives them immediately, while node 3 experiences a delay. Before node 3 synchronizes, node 2 initiates its own update, which node 3 receives promptly. Consequently, node 1 and 2 record the write order x=1,x=2, whereas node 3 records x=2,x=1, causing inconsistency.

Paxos ensures that all nodes reach absolute agreement, preventing such chaos.

Basic Idea of Paxos

Each change to data is called a proposal . The algorithm involves three roles:

Proposer – initiates a proposal

Acceptor – votes on proposals

Learner – learns the outcome (can be ignored for the core algorithm)

Proposer and Acceptor form the committee; Learner only receives the accepted proposal.

The execution consists of two phases:

(1) Prepare Phase : The proposer asks each acceptor whether it may propose.

(2) Accept Phase : If a majority of acceptors agree, the proposal is accepted and becomes the new value.

Each acceptor maintains three variables:

minProposal – the smallest proposal number it has seen

acceptedProposal – the highest proposal number it has accepted

acceptedValue – the value associated with the accepted proposal

Below is a flowchart illustrating the process:

Applying Paxos to the earlier example yields the following sequence:

Node 1 receives request x=1, becomes the proposer, obtains proposal number 1, and after receiving acceptance from other nodes sends accept(1,1). The acceptance is delayed for nodes 2 and 3, so the proposal does not yet become effective.

Node 2 then proposes x=2. Because node 1 has already accepted (1,1), it returns this information to node 2, which adopts it and sends accept(2,1). All nodes eventually record the proposal, and the system converges on the same value.

Later, when node 1’s delayed accept(1,1) arrives, its proposal number (1) is lower than the already accepted number (2), so it is rejected, preserving consistency.

Three Typical Paxos Scenarios

For illustration, the following examples use five nodes.

1. A committed proposal is learned by later proposals

Node 1 proposes with number 1 and obtains agreement from three nodes, making the proposal effective. Node 2 then proposes number 2; node 3, seeing a higher number, agrees and returns its accepted proposal (1,x). Node 5 selects the highest returned proposal number as its own value and sends accept(2,x). All nodes accept, resulting in a consistent value x.

2. An uncommitted but accepted proposal influences later proposals

Node 1’s proposal is only accepted by node 3 due to network issues. Node 5 later proposes; node 3, seeing a higher number, agrees and returns its accepted proposal (1,x). Node 5 adopts x as its value and sends accept(2,x). After acceptance, all nodes converge on x.

3. An earlier proposal fails, a later one succeeds

Node 1’s proposal gains agreement from nodes 1, 2, 3, but node 1 accepts first because of network delays. Before nodes 2 and 3 accept, node 5 proposes with a higher number; nodes 3, 4, 5 accept it. When node 3 later receives node 1’s accept request, it rejects it because its recorded proposal number (2) exceeds node 1’s (1). Node 5’s proposal y becomes effective, and all nodes end up with value y, while node 1’s proposal is discarded.

Summary

The above outlines the fundamental concepts of Paxos. For deeper understanding, refer to the following articles:

https://segmentfault.com/a/1190000018844326

https://zh.wikipedia.org/zh-cn/Paxos算法