Paxos

The first industrial solution to the consensus problem, and the theoretical root of all subsequent protocols (Raft, ZAB). The three-round message exchange of Basic Paxos (prepare/promise/accept) seems simple, but every step from single decision to continuous logs (Multi-Paxos) is fraught with pitfalls—this is the direct motivation for the birth of Raft.

Paxos (Leslie Lamport, 1989/1998) is the first industrial solution to the consensus problem and the theoretical root of all subsequent consensus protocols (VR, ZAB, Raft). However, Lamport's original description is written as an analogy to the Greek parliament, making it obscure and difficult to understand—"The Part-Time Parliament". The design motivation for Raft was "to make Paxos understandable to ordinary engineers".

Basic Paxos

Paxos solves single consensus: how multiple nodes can reach an agreement on a single value.

Roles

• Proposer: Initiates a proposal (the client is usually the proposer)
• Acceptor: Votes and stores the accepted value (usually N=2f+1 nodes, tolerating f failures)
• Learner: Learns the final decided value from the acceptors

In actual implementations, each node usually assumes all three roles simultaneously.

Two-Phase Protocol

Phase 1: Prepare/Promise

Proposer:
  Choose a proposal number N (must be greater than any number it has used before, and globally unique)
  Send Prepare(N) → All Acceptors (to a majority)

Acceptor:
  Upon receiving Prepare(N):
    if N > any Prepare number it has seen before:
      Promise: Do not accept any proposal with a number < N
      Reply with Promise(N, previously accepted value: {N_highest, V})
    else:
      Ignore (or reply with rejection)

Phase 2: Accept/Accepted

Proposer:
  Wait for a majority of Promise replies
  If a majority is received:
    → Prepare to send Accept!
    Choose value:
      if any Promise contained an already accepted value:
        Choose V corresponding to N_highest (i.e., the accepted value with the highest sequence number) ← Key point!
      else:
        Choose any value you wish
    Send Accept(N, V) → All Acceptors

Acceptor:
  Upon receiving Accept(N, V):
    if N >= the minimum N this acceptor has promised (i.e., it has not promised a prepare with a number > N):
      Accept: Store (N, V)
      Reply with Accepted(N)
    else:
      Reject

Why Two Phases?

The purpose of Phase 1 is learning: the Proposer uses Prepare/Promise to determine "whether a value has already been partially accepted". If so, it must use that value instead of its own—this prevents proposals from different proposers from overwriting each other.

Counter-example: If Phase 1 is skipped, two proposers might simultaneously propose different values, each obtaining a majority of accepts, but their majorities do not overlap → both values become "locked" → the system can never converge.

Why N Must Be Monotonically Increasing

If Proposer A proposes V1 with N=1, but hasn't received a majority of accepts yet; and Proposer B proposes V2 with N=2. The Phase 1 Prepare(2) in the second round will cause acceptors to promise not to accept any N<2—A's Accept(1,V1) will be rejected.

This ensures that only one value is accepted by a majority in the end.

Multi-Paxos

Basic Paxos solves single consensus. Continuous consensus rounds (such as each entry in a replicated log) constitute Multi-Paxos.

Optimization: Elect a Stable Leader

If every round requires the full two-phase Prepare + Accept → 2 RTTs per entry. After Multi-Paxos elects a stable leader, that leader can skip Phase 1—because as long as it remains the leader, no other proposer will compete.

Leader first elected: Phase 1 Prepare/Promise (determine leader identity and highest accepted N)
Subsequent entries: Directly Phase 2 Accept → 1 RTT per entry
New proposer wants to become leader: It sends Phase 1 Prepare and gets a majority → It becomes the new leader

Paxos vs Raft

Paxos defines the core consensus mechanism but does not define:

• Leader election algorithm (it only says "elect a distinguished proposer")
• Log compaction/snapshot mechanism
• Membership change protocol

This led every Paxos implementation (Google Chubby, Amazon DynamoDB, Microsoft Azure Storage) to reinvent these parts—the implementation complexity ended up being higher than that of Raft.

References

• Paper: "The Part-Time Parliament" (Lamport, 1998)
• Paper: "Paxos Made Simple" (Lamport, 2001) — A more readable version
• Paper: "Paxos Made Live — An Engineering Perspective" (Google Chubby team, 2007)

Keywords: Paxos, Basic Paxos, Multi-Paxos, Prepare/Promise, Accept/Accepted, proposal number, distinguished proposer