Elijah's Notes

Paxos Introduction

3 min read

Purpose

This note is a first pass at Paxos. It states the impossibility result that shapes the design, then walks the two phases of the core protocol in the setting where Paxos actually gets used, state machine replication. Paxos Made Simple has the full derivation.

FLP impossibility result

The FLP result shows that in an asynchronous system where even one process may fail, no deterministic protocol can guarantee consensus terminates. You cannot have guaranteed safety and guaranteed progress at once, so a protocol has to pick which one it will never give up.

Paxos always picks safety. It still makes progress in practice as long as a majority of nodes are up and failures stop long enough for a round to complete, which is the best FLP allows.

FLP in one sentence

You cannot guarantee both safety and liveness in an asynchronous system with even one faulty process, so every consensus protocol must choose which property it will sacrifice under adversarial conditions.

State machine replication

Order client operations into an append-only log and have every replica apply the log in order. Consensus is easy if only one request is in flight at a time, so the standard structure is to elect a leader, send all client requests to it, and let the leader define the ordering. If the leader fails or gets slow, elect a new one, as many times as needed. Each log slot then needs all nodes to agree on one value, and that per-slot agreement is exactly what Paxos provides. It also makes leader election safe, since competing would-be leaders cannot commit conflicting values.

State machine replication

One Paxos instance per log slot. The value chosen for slot i is the ith command everyone executes.

Paxos, the algorithm

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

    Note over P,A3: Phase 1: Prepare/Promise
    P->>A1: Prepare(n=1)
    P->>A2: Prepare(n=1)
    P->>A3: Prepare(n=1)
    A1-->>P: Promise(n=1, ⊥)
    A2-->>P: Promise(n=1, ⊥)
    A3-->>P: Promise(n=1, ⊥)
    Note over P: Majority promised, no prior value

    Note over P,A3: Phase 2: Accept/Accepted
    P->>A1: Accept(n=1, v="X")
    P->>A2: Accept(n=1, v="X")
    P->>A3: Accept(n=1, v="X")
    A1-->>P: Accepted(n=1, v="X")
    A2-->>P: Accepted(n=1, v="X")
    A3-->>P: Accepted(n=1, v="X")
    Note over P,A3: Value "X" is chosen (majority accepted)

Proposer:
  Prepare(n) -> Promise(n, n', v')
  Accept(n, v) -> Accepted(n, v)
 
Acceptor:
  Promise(n, n', v') -> Prepare(n)
  Accepted(n, v) -> Accept(n, v)

Phase 1: Prepare

  • The proposer selects a proposal number and sends Prepare(n) to all (or a majority) of the acceptors.
  • An acceptor that has seen nothing higher than responds with Promise(n, n', v'), where is the highest proposal number it has accepted and is the value of that proposal. The promise means the acceptor will never accept a proposal numbered less than .
  • The proposer waits for a majority of promises before proceeding.

Phase 2: Accept

  • Once the proposer has a majority of promises, it sends Accept(n, v) to the acceptors, where is the value of the highest-numbered proposal reported in the promises, or the proposer’s own value if no promise reported one. Adopting the highest reported value is what keeps an already-chosen value from being overwritten.
  • Each acceptor that has not promised a higher number accepts and responds with Accepted(n, v).
  • Once a majority of acceptors accept, the value is chosen.

Graph View