Paxos Algorithm

Overview

Paxos is the foundational consensus algorithm, first described by Leslie Lamport in 1989 (published 1998). It allows a distributed system to agree on a single value even if nodes crash or messages are lost. Despite its reputation for complexity, Paxos is the basis for many production systems including Google’s Chubby lock service and Spanner database.

The Problem

How do distributed nodes agree on one value when:

• Messages can be lost, duplicated, or reordered
• Nodes can crash and restart
• There is no global clock

Roles in Paxos

Paxos defines three roles (a node can play multiple roles):

graph LR
    P[Proposer] -->|Proposes values| A[Acceptor]
    A -->|Accepted values| L[Learner]
    P -.->|Can also be| L
    A -.->|Can also be| P

The Two Phases

Phase 1: Prepare

The proposer selects a proposal number n (must be unique and higher than any previous number) and sends a PREPARE(n) message to a majority of acceptors.

sequenceDiagram
    participant P as Proposer
    participant A1 as Acceptor 1
    participant A2 as Acceptor 2
    participant A3 as Acceptor 3
    
    P->>A1: PREPARE(n)
    P->>A2: PREPARE(n)
    P->>A3: PREPARE(n)
    
    A1-->>P: PROMISE(n, {n_a1, v_a1})
    A2-->>P: PROMISE(n, {n_a2, v_a2})
    A3-xP: (no response - crashed)
    
    Note over P: Majority (2/3) promised

When an acceptor receives PREPARE(n):

• If n is higher than any prepare it has responded to: it promises not to accept proposals numbered less than n, and returns the highest-numbered proposal it has accepted (if any)
• If n is lower than a prepare it already responded to: it ignores or sends a NACK

Phase 2: Accept

If the proposer receives promises from a majority of acceptors, it sends ACCEPT(n, v) where:

• v is the value of the highest-numbered proposal among the promises received
• If no acceptor had accepted a proposal, the proposer can choose its own value

sequenceDiagram
    participant P as Proposer
    participant A1 as Acceptor 1
    participant A2 as Acceptor 2
    participant A3 as Acceptor 3
    
    Note over P: Highest accepted was (n_a2, v_a2)
    P->>A1: ACCEPT(n, v_a2)
    P->>A2: ACCEPT(n, v_a2)
    P->>A3: ACCEPT(n, v_a2)
    
    A1-->>P: ACCEPTED(n, v_a2)
    A2-->>P: ACCEPTED(n, v_a2)
    
    Note over P: Majority accepted → v_a2 is decided!

When an acceptor receives ACCEPT(n, v):

• If it has not promised to ignore proposals numbered n: it accepts the proposal
• Otherwise: it ignores the request

Phase 3: Learn (Optional)

Once a value is accepted by a majority, learners are notified of the decided value.

Complete Paxos Example

sequenceDiagram
    participant P1 as Proposer 1 (n=1)
    participant P2 as Proposer 2 (n=2)
    participant A1 as Acceptor 1
    participant A2 as Acceptor 2
    participant A3 as Acceptor 3
    
    Note over P1: Phase 1: Prepare
    P1->>A1: PREPARE(1)
    P1->>A2: PREPARE(1)
    A1-->>P1: PROMISE("1, null")
    A2-->>P1: PROMISE("1, null")
    
    Note over P2: Higher proposal arrives
    P2->>A2: PREPARE(2)
    P2->>A3: PREPARE(2)
    A2-->>P2: PROMISE("2, null")
    A3-->>P2: PROMISE("2, null")
    
    Note over P1: Phase 2: Accept (using own value)
    P1->>A1: ACCEPT("1, #quot;X#quot;")
    P1->>A2: ACCEPT("1, #quot;X#quot;")
    Note over A2: ignores (promised 2)
    A1-->>P1: ACCEPTED("1, #quot;X#quot;")
    Note over P1: Only 1/3 accepted, no majority
    
    Note over P2: Phase 2: Accept
    P2->>A2: ACCEPT("2, #quot;Y#quot;")
    P2->>A3: ACCEPT("2, #quot;Y#quot;")
    A2-->>P2: ACCEPTED("2, #quot;Y#quot;")
    A3-->>P2: ACCEPTED("2, #quot;Y#quot;")
    Note over P2: 2/3 accepted → "Y" is decided!

Multi-Paxos

Basic Paxos decides a single value. To agree on a sequence of values (a log), running Paxos for each entry is expensive. Multi-Paxos optimizes this:

graph TD
    subgraph "Basic Paxos"
        B1[Entry 1: 2 phases] --> B2[Entry 2: 2 phases]
        B2 --> B3[Entry 3: 2 phases]
    end
    subgraph "Multi-Paxos"
        M1[Entry 1: 2 phases - elect leader] --> M2[Entry 2: 1 phase - skip prepare]
        M2 --> M3[Entry 3: 1 phase - skip prepare]
    end

Key Optimizations

1. Stable Leader: A single proposer is elected as leader. Once elected, it skips Phase 1 for subsequent proposals.
2. Log Replication: Each entry in the log is a separate Paxos instance, but the leader only runs Phase 1 once.
3. Leader Lease: The leader maintains a lease to avoid conflicts.

Multi-Paxos Flow

sequenceDiagram
    participant L as Leader
    participant F1 as Follower 1
    participant F2 as Follower 2
    
    Note over L: Initial: Full Paxos for entry 1
    L->>F1: PREPARE(n)
    L->>F2: PREPARE(n)
    F1-->>L: PROMISE(n)
    F2-->>L: PROMISE(n)
    L->>F1: ACCEPT(n, v1)
    L->>F2: ACCEPT(n, v1)
    
    Note over L: Skip prepare for entries 2, 3...
    L->>F1: ACCEPT(n, v2)
    L->>F2: ACCEPT(n, v2)
    L->>F1: ACCEPT(n, v3)
    L->>F2: ACCEPT(n, v3)

Fast Paxos

Fast Paxos reduces latency by allowing clients to send values directly to acceptors, bypassing the leader:

sequenceDiagram
    participant C as Client
    participant L as Leader
    participant A1 as Acceptor 1
    participant A2 as Acceptor 2
    participant A3 as Acceptor 3
    
    Note over L: Phase 1 (once)
    L->>A1: PREPARE(n)
    L->>A2: PREPARE(n)
    L->>A3: PREPARE(n)
    
    Note over C: Client sends directly
    C->>A1: ACCEPT(fast, v)
    C->>A2: ACCEPT(fast, v)
    C->>A3: ACCEPT(fast, v)
    
    Note over L: If collision detected, fall back to classic Paxos

Trade-off: Fast Paxos requires a larger quorum (⌈3n/4⌉+1 instead of ⌈n/2⌉+1) to handle collisions.

Paxos vs. Raft

Real-World Usage

Google Chubby

Google’s distributed lock service, used internally for:

• Leader election for Google services
• Configuration management
• Distributed locking

Chubby uses Multi-Paxos with a stable leader to replicate a distributed lock table across 5 replicas. Clients interact via a file-system-like API.

Google Spanner

Spanner uses Paxos for replication within each shard:

graph TD
    subgraph "Spanner Shard"
        P1[Paxos Group<br/>5 replicas] --> DB1["(Shard Data)"]
        P1 -->|TrueTime API| TT[GPS + Atomic Clocks]
    end
    subgraph "Another Shard"
        P2[Paxos Group<br/>5 replicas] --> DB2["(Shard Data)"]
    end
    P1 -->|2PC| P2

Key innovation: TrueTime API provides bounded clock uncertainty, enabling globally consistent reads without locking.

Paxos vs. Raft: Deep Comparison

graph TD
    subgraph "Multi-Paxos"
        MP_L["Leader (proposer)"] --> MP_A1[Acceptor 1]
        MP_L --> MP_A2[Acceptor 2]
        MP_L --> MP_A3[Acceptor 3]
        MP_L -->|"Can have gaps"| MP_LOG[Log: 1, 2, _, 5, 6]
    end
    subgraph "Raft"
        R_L[Leader] --> R_F1[Follower 1]
        R_L --> R_F2[Follower 2]
        R_L -->|"No gaps"| R_LOG[Log: 1, 2, 3, 4, 5]
    end

Why Raft Won

Despite Paxos being theoretically equivalent, Raft dominates modern systems because:

1. Single specification: Paxos has many variants (Classic, Multi, Fast, Cheap, Flexible, Byzantine). Each implementation makes different choices.
2. Strong leader model: Raft’s leader-only-writes simplifies reasoning. Paxos allows any proposer to propose.
3. Log structure: Raft’s contiguous log makes replication straightforward. Paxos allows gaps, complicating recovery.
4. Membership changes: Raft has a well-defined mechanism (joint consensus). Paxos requires ad-hoc solutions.
5. Educational material: The Raft paper, interactive visualizations (raft.github.io), and reference implementation made it accessible.

Interview Questions

1. Explain the two phases of Paxos.

   • Phase 1 (Prepare): Proposer sends PREPARE(n) to majority; acceptors promise not to accept lower-numbered proposals. Phase 2 (Accept): Proposer sends ACCEPT(n,v) to majority; value is decided if majority accepts.

2. What happens if two proposers compete in Paxos?

   • They can livelock by continuously overriding each other’s proposals. Multi-Paxos solves this with a stable leader.

3. Why does Paxos require a majority quorum?

   • Any two majorities must overlap by at least one node, ensuring that if one majority accepted a value, a later majority will learn about it.

4. What is the difference between Paxos and Multi-Paxos?

   • Paxos decides one value. Multi-Paxos decides a sequence of values by electing a stable leader that skips Phase 1 for subsequent entries.

5. How does Fast Paxos differ from classic Paxos?

   • Fast Paxos allows clients to send directly to acceptors (1 fewer round-trip) but requires a larger quorum (3n/4+1) to handle collisions.

Common Mistakes

• Thinking Paxos is simple — it’s notoriously hard to implement correctly
• Confusing proposal numbers with values — proposal numbers are for ordering, values are the data
• Forgetting that Paxos requires majority quorums, not just any majority of nodes
• Assuming Paxos handles Byzantine faults — it only handles crash faults
• Not handling dueling proposers (livelock) in basic Paxos

Summary

Paxos is the theoretical foundation of consensus in distributed systems. While complex, understanding its two-phase prepare-accept mechanism is essential. Multi-Paxos extends it to log replication with a stable leader, and Fast Paxos optimizes for latency. Most production systems use Raft (which is equivalent to Multi-Paxos) for its clarity.

Cross-References

• Consensus Overview — Where Paxos fits in the landscape
• Raft Consensus — A more understandable alternative
• ZAB — ZooKeeper’s similar protocol
• Primary-Backup Replication — Uses consensus for failover
• Service Discovery — Often built on consensus (etcd uses Raft)