What Is Paxos? A Storytelling Guide to Distributed Consensus

First, a story

In a dark Greek city‑state called Paxos ruled by King Leslie Lamport, three groups of people exist: decision makers (Acceptors), proposers, and the crowd (Clients/Learners). Although the city claims to be democratic, proposals must pass through proposers to decision makers, who are odd in number so that a simple majority decides.

The twist is that proposers bribe decision makers: the richer the bribe, the more likely a proposal is chosen. This leads to a two‑stage bidding process.

Stage One

Decision makers accept any offer higher than their current one without notifying earlier bidders.

Proposers submit offers to all decision makers; if a majority accept, they stop bidding.

At the end of Stage One each proposer believes a majority accepted its offer, and the decision‑maker group converges on the highest offer.

Stage Two

Proposers approach the decision makers who have already paid them, encountering three possible outcomes: the decision maker takes a higher bribe and returns to Stage One, the decision maker keeps the proposer’s offer and the proposal succeeds, or the contract is already signed elsewhere and the proposer must switch to that proposal.

After Stage Two all proposers hold the same proposal and all decision makers accept the same one, which is then announced to the crowd.

Now, the real Paxos

What is Paxos? Paxos is a distributed consensus algorithm that forms the foundation of many consistency protocols. It solves the problem of reaching agreement on a value in a system where processes may crash, be restarted, and messages may be delayed, lost, or duplicated (excluding Byzantine faults).

In distributed systems there are two communication models: shared memory and message passing. Paxos operates on the message‑passing model.

The algorithm guarantees that despite the above failures, a single value is chosen and all nodes eventually learn it, ensuring a consistent state across the system.

Four roles are defined:

Acceptor – the decision maker

Proposer – the entity that suggests values

Client – the originator of the request (the crowd)

Learner – the node that learns the final decision

Phase One (Prepare)

Proposer sends a Prepare(N) request with a proposal number N to a majority of Acceptors.

If an Acceptor receives a Prepare(N) with N larger than any it has responded to before, it replies with the highest-numbered proposal it has accepted (if any) and promises not to accept proposals with numbers lower than N.

If the proposer does not receive responses from a majority, it increments N and retries.

Phase Two (Accept)

Once a proposer obtains a majority of Prepare responses, it sends an Accept(N, value) request to that majority.

An Acceptor accepts the proposal if it has not already promised to a higher-numbered proposal.

Only a value that receives a majority of Accept messages becomes chosen, and Learners are then informed of the chosen value.

Common questions

Why multiple Acceptors? A single Acceptor would be a single point of failure; multiple Acceptors provide fault tolerance.

Why require a majority? Two different majorities cannot exist simultaneously, ensuring that at any time only one value can be chosen.

Why can Acceptors hold multiple proposals? Allowing multiple proposals prevents deadlock when no single proposal can achieve a majority.

What if many Proposers exist? It becomes harder for any one proposer to obtain a majority, slowing convergence.

Why include proposal numbers? Numbers allow Acceptors to compare proposals and choose the most recent one, avoiding inconsistencies caused by message reordering.

Beyond basic Paxos

To speed up convergence, some implementations introduce a single leader that acts as the sole Proposer. This creates a new single point of failure, so leader election mechanisms are added, leading to variants such as Multi‑Paxos and eventually the ZAB protocol used by ZooKeeper.