Paxos

Basic, single-decree Paxos: two proposers, five acceptors, and one value they have to agree on. Crash nodes, drop packets, start a duel, and watch it stay safe.

Scenario

    paused t = 0.00s 5/5 acceptors up · quorum 3 chosen nothing yet
    • prepare
    • promise
    • accept
    • accepted
    • nack
    • decide
    • P1: moon
    • P2: star
    Propose
    Crash / revive

    Click a node to crash or revive it. Keys: Space play/pause, → step, R reset.Tap a node to crash or revive it.

    Event log

      The whole algorithm

      1. 1a prepare

        A proposer picks a ballot number n higher than any it has seen (P1 uses odd numbers, P2 even, so they never collide) and sends PREPARE(n) to the acceptors.

      2. 1b promise

        If an acceptor hasn't promised anything higher, it promises to ignore every ballot below n and reports the highest-numbered proposal it has already accepted, if any. Otherwise it answers NACK.

      3. 2a accept

        With promises from a majority, the proposer sends ACCEPT(n, v). If any promise reported an accepted proposal, v must be the value from the highest-numbered one. Only if none did can the proposer use its own value.

      4. 2b accepted

        An acceptor accepts (n, v) unless it has since promised a higher ballot.

      5. learn

        v is chosen the moment a majority accepts the same ballot. A proposer that collects a majority of ACCEPTED replies knows this and tells everyone with DECIDE.

      Why it's safe: any two majorities of five acceptors share at least one member. Once v is chosen, every later quorum contains an acceptor that accepted it. The highest ballot reported in phase 1 therefore always carries v, and rule 2a makes every later proposer propose v again. Crashes, lost packets and duels can stall Paxos, but they can't make it change its mind.

      Basic vs. Multi-Paxos: this page decides a single value. Multi-Paxos runs one of these instances per slot in a replicated log, and lets a stable leader run phase 1 once and then skip straight to ACCEPT for each new slot. That is the optimization in the multi-leader MySQL animation that inspired this page.