How Paxos Guarantees Strong Consistency in Distributed Systems

Distributed consistency algorithms ensure that data across multiple nodes in a distributed system eventually reaches the same state, despite network delays, failures, or other issues.

1. Introduction to Paxos Algorithm

Paxos is a strong consistency algorithm, meaning that at any moment every node sees the same data and any operation is immediately reflected throughout the system.

The diagram shows three nodes; clients 1 and 2 attempt to modify the node values, and Paxos guarantees that all nodes end up with the same value (either all value1 or all value2).

Paxos involves three roles:

Proposer : initiates a proposal; if a majority of acceptors accept it, the proposer considers the value chosen.

Acceptor : accepts proposals and promises not to accept any proposal with a lower number than one it has already accepted.

Learner : learns which value has been chosen from the acceptors.

2. Paxos Workflow

2.1 Prepare Phase

The proposer (client) sends a prepare request with a proposal number to the acceptors (cluster nodes). The request does not contain the actual value.

Assume client 1 uses proposal number 0 and client 2 uses number 3. Nodes A, B, and C receive these requests for the first time and respond accordingly.

Node A, having no prior proposal, replies “no proposal” and promises not to accept any proposal with a number lower than 0. Nodes B and C behave similarly.

When client 1 later contacts node C, node C has already promised to a higher-numbered proposal (3), so it discards client 1’s request.

Client 2’s request (number 3) is accepted by nodes A and B, which respond “no proposal” but keep their promise for higher numbers.

At this point the prepare phase is complete because the proposer has received responses from a majority of nodes.

2.2 Accept Phase

After a successful prepare, the proposer sends the actual value together with its proposal number. Client 1’s request is rejected because nodes have promised not to accept numbers lower than 3, while client 2’s request is accepted, synchronizing the value across the cluster.

If a learner is present, it receives the chosen value from the majority of acceptors and stores it.

3. Handling New Proposals After Partial Acceptance

Suppose nodes A and B have already accepted proposal (3, "xia"), node C has none, and a new client 3 proposes number 6.

Nodes A and B return their accepted proposal (3, "xia"), while node C returns “no proposal”.

Client 3 updates the proposal to (6, "xia") based on the highest received number and sends it to all nodes.

All nodes accept this higher-numbered proposal, achieving consensus.

Summary

Paxos is a strong consistency distributed algorithm that ensures all nodes in a system agree on the same data.

The algorithm consists of a prepare phase and an accept phase, with a guarantee that nodes will not accept proposals with numbers lower than those they have already promised.