Abstract

The Paxos algorithm, when presented in plain English, is very simple. Leslie Lamport’s “Paxos Made Simple” (2001) is a re-explanation of his original 1998 paper “The Part-Time Parliament,” which described the algorithm through an allegory about a fictional Greek island’s parliamentary system. The re-explanation strips away the allegory and presents the algorithm directly. Paxos solves the fundamental problem of getting a collection of distributed processes to agree on a single value, even when processes may fail and messages may be lost or delayed.

Historical Context

The Problem Before Paxos

Before Paxos, distributed systems had no rigorous, proven algorithm for consensus that could tolerate arbitrary process failures and message delays. Engineers built ad-hoc solutions that either:

• Assumed reliable networks — which break catastrophically in production when networks partition
• Used two-phase commit (2PC) — which blocks if the coordinator fails, making it unsuitable for highly available systems
• Relied on physical time synchronization — which is fundamentally unreliable across data centers

Leslie Lamport, working at SRI International and later Microsoft Research, formalized the consensus problem and proved that Paxos solves it correctly under the asynchronous model (no timing assumptions) as long as a majority of processes remain operational.

Publication History

The original paper, “The Part-Time Parliament” (1998), was submitted in 1990 but rejected by reviewers who didn’t appreciate the Greek island allegory. It was finally published in ACM Transactions on Computer Systems. “Paxos Made Simple” (2001) was Lamport’s response to complaints that the original was too difficult to understand — the re-explanation is only 14 pages and begins with the now-famous line: “The Paxos algorithm, when presented in plain English, is very simple.”

Key Concepts

The Consensus Problem

The consensus problem requires a set of processes to agree on a single value such that:

1. Validity: Only a value that was proposed can be chosen
2. Agreement: All processes that decide must decide on the same value
3. Termination: Eventually, some value is chosen (liveness, requires partial synchrony)

The Three Roles

Paxos defines three roles (a single process can play multiple roles):

• Proposer: Proposes values to be agreed upon
• Acceptor: Votes on proposals and remembers what they’ve accepted
• Learner: Learns the chosen value once consensus is reached

The Two-Phase Protocol

Phase 1: Prepare

1. A proposer selects a proposal number n (must be unique and higher than any it has used before)
2. It sends a Prepare(n) request to a majority of acceptors
3. Each acceptor responds with:
   • A promise not to accept any proposal numbered less than n
   • The highest-numbered proposal it has already accepted (if any)

Phase 2: Accept

1. If the proposer receives responses from a majority:
   • If any acceptor reported an already-accepted value, the proposer must propose that value (this ensures safety)
   • Otherwise, it can propose any value
2. It sends Accept(n, value) to the acceptors
3. Each acceptor accepts the proposal unless it has already promised to a higher-numbered proposal

sequenceDiagram
    participant P as Proposer
    participant A1 as Acceptor 1
    participant A2 as Acceptor 2
    participant A3 as Acceptor 3

    Note over P: Phase 1: Prepare
    P->>A1: Prepare(n=1)
    P->>A2: Prepare(n=1)
    P->>A3: Prepare(n=1)

    A1-->>P: Promise(n=1, no prior)
    A2-->>P: Promise(n=1, no prior)
    A3-->>P: Promise(n=1, no prior)

    Note over P: Phase 2: Accept
    P->>A1: Accept(n=1, v="X")
    P->>A2: Accept(n=1, v="X")
    P->>A3: Accept(n=1, v="X")

    A1-->>P: Accepted
    A2-->>P: Accepted
    A3-->>P: Accepted

    Note over P: Value "X" is chosen!

Why Paxos is Safe

The key insight is that once a value is chosen (accepted by a majority), any future proposer that completes Phase 1 will learn about that value (because any majority overlaps with the majority that accepted it). The proposer is then forced to re-propose that same value, ensuring agreement is never violated.

This is often called the “majority overlap” property — any two majorities share at least one member, so information about chosen values can never be lost.

Multi-Paxos

Basic Paxos chooses a single value. Real systems need to agree on a sequence of values (a replicated log). Multi-Paxos optimizes this by:

1. Electing a stable leader that acts as the distinguished proposer
2. Skipping Phase 1 for subsequent log entries (the leader’s prepare applies to all future slots)
3. Only running Phase 2 for each new log entry

This reduces consensus from 2 round-trips to 1 round-trip per log entry in the common case (no leader changes).

graph TD
    subgraph "Basic Paxos (per value)"
        A[Phase 1: Prepare] --> B[Phase 2: Accept]
    end

    subgraph "Multi-Paxos (stable leader)"
        C[Phase 1: Prepare - ONCE] --> D[Phase 2: Accept slot 1]
        D --> E[Phase 2: Accept slot 2]
        E --> F[Phase 2: Accept slot 3]
        F --> G[...]
    end

How It Works in Practice

Handling Competing Proposers

When two proposers compete (called “dueling proposers” or “livelock”):

1. Proposer A sends Prepare(n=1)
2. Proposer B sends Prepare(n=2) — higher, so acceptors promise to B
3. Proposer A’s Accept(n=1) is rejected
4. Proposer A retries with Prepare(n=3) — higher, so acceptors promise to A
5. Proposer B’s Accept(n=2) is rejected
6. This can repeat indefinitely…

The solution is leader election: designate one proposer as the leader. Only the leader proposes. If the leader fails, a new leader is elected. This is why Multi-Paxos includes leader election.

Failure Handling

Paxos tolerates f failures in a cluster of 2f + 1 nodes:

The algorithm is safe under any failure pattern (even Byzantine if extended to Byzantine Paxos). It sacrifices liveness during periods when no majority is available (consistent with the FLP impossibility result).

Impact & Legacy

Systems That Use Paxos (or Variants)

Paxos vs. Raft

Raft (2014) was explicitly designed as a more understandable alternative to Paxos. Key differences:

Why Paxos is Hard

Lamport himself noted that Paxos is simple, but implementing it in production is extraordinarily difficult. Google engineers reported that:

“There are significant gaps between the description of the Paxos algorithm and the needs of a real-world system… We used the Paxos algorithm as the base for a framework that implements a fault-tolerant log. We then relied on the log to build a fault-tolerant database.” — “Paxos Made Live” (Chandra, Griesemer, Redstone, 2007)

The gaps include: leader election, group membership changes, snapshotting, state transfer to new replicas, and handling disk corruption.

Key Takeaways

• Paxos solves consensus: It guarantees agreement among distributed processes despite failures, with only the assumption that a majority of nodes are operational
• Majority overlap is the key insight: Any two majorities share at least one member, which prevents conflicting decisions
• Multi-Paxos is what production systems use: Basic Paxos is a building block; real systems need a replicated log (Multi-Paxos)
• Simple algorithm, hard implementation: The gap between the algorithm and a production system is vast (leader election, membership changes, snapshotting)
• Raft is functionally equivalent: If you understand Raft, you understand the core of Paxos — Raft just makes the engineering choices that Paxos leaves open
• Every distributed database relies on consensus: Whether they call it Paxos, Raft, ZAB, or Viewstamped Replication, the underlying principles are the same

Interview Relevance

Paxos concepts appear frequently in system design interviews:

• “How does distributed consensus work?” — Explain the two-phase protocol, majority quorums, and why safety is guaranteed
• “Design a distributed configuration store” — This is essentially building a system like ZooKeeper/etcd on top of Paxos/Raft
• “How does Google Spanner achieve global consistency?” — Paxos groups + TrueTime for external consistency
• “What’s the difference between Paxos and 2PC?” — 2PC blocks on coordinator failure; Paxos can make progress with any majority
• “Can you have both consistency and availability?” — Connect to CAP theorem; Paxos chooses CP, requiring a majority for progress