Paxos Consensus Flow: Mermaid Diagram

About Source

Paxos is a family of protocols for achieving consensus in a distributed network of unreliable processors, originally described by Leslie Lamport, guaranteeing that a single value will be chosen among proposed values even if a minority of nodes fail or messages are delayed.

The core Single-Decree Paxos protocol involves three roles: Proposers (clients initiating a value), Acceptors (the quorum that votes), and Learners (nodes that learn the chosen value). The protocol proceeds in two phases.

Phase 1 — Prepare/Promise: A proposer selects a unique proposal number n (strictly greater than any previously used) and broadcasts a Prepare(n) message to a quorum of acceptors. Each acceptor that receives Prepare(n) responds with a Promise — a guarantee not to accept any proposal numbered less than n. If the acceptor has already accepted a value under a lower proposal number, it includes that value in its Promise response.

Phase 2 — Accept/Accepted: If the proposer receives promises from a majority, it broadcasts an Accept(n, v) message. The value v is either the proposer's own proposed value (if no acceptor had previously accepted anything) or the value associated with the highest-numbered prior promise. Each acceptor that has not since promised to ignore proposals less than n accepts the value and replies Accepted(n, v). Once a majority replies Accepted, the value is chosen.

Multi-Paxos optimizes repeated consensus rounds by electing a stable leader (the Distinguished Proposer), allowing Phase 1 to be skipped for subsequent decisions as long as the leader remains stable. This is how Paxos powers systems like Google Chubby and Spanner. Compare this two-phase structure with Raft Consensus Algorithm, which makes leader election an explicit first-class concept rather than an optimization. Data Replication Strategy shows how consensus integrates into a broader replication pipeline.

Frequently asked questions

Paxos is a family of distributed protocols that guarantees a cluster of nodes agrees on a single value even if a minority of nodes fail or messages are lost. Proposed by Leslie Lamport, it defines three roles — Proposers, Acceptors, and Learners — and proceeds in two phases to achieve a durable, consistent decision.

In Phase 1 (Prepare/Promise) a Proposer broadcasts a proposal number `n` to a quorum of Acceptors; each Acceptor promises not to accept older proposals and returns any value it has already accepted. In Phase 2 (Accept/Accepted) the Proposer sends its chosen value to the quorum; once a majority replies Accepted, the value is chosen and learners are notified.

Paxos is appropriate when you need a proven theoretical foundation for a custom consensus layer, or when operating within an ecosystem that already uses it (Google Chubby, Spanner, Apache Zookeeper's ZAB variant). For greenfield projects, Raft's clearer structure and richer library ecosystem are usually preferable.

Common errors include failing to persist proposal numbers to stable storage (allowing a restarted node to reuse old numbers), incorrectly handling the "value from highest prior promise" rule in Phase 2, and not implementing a distinguished leader for Multi-Paxos — causing repeated Phase 1 round-trips that destroy performance.

Paxos defines the minimal safety properties but leaves many design choices open — leader selection, log management, membership changes — which makes complete implementations diverge and are hard to audit. Raft prescribes all of these explicitly, making independent implementations interoperable and easier to verify. Both tolerate up to ⌊(N−1)/2⌋ simultaneous failures in an N-node cluster.

mermaid

flowchart TD
    A([Proposer selects\nproposal number n]) --> B[Phase 1a: Broadcast\nPrepare n to quorum]
    B --> C[Acceptor 1]
    B --> D[Acceptor 2]
    B --> E[Acceptor 3]
    B --> F[Acceptor 4]
    B --> G[Acceptor 5]

    C --> H{Has accepted\nhigher n?}
    D --> H
    E --> H
    H -->|No| I[Promise n\nwith highest accepted value]
    H -->|Yes| J[Reject — already\npromised higher n]

    I --> K{Majority\npromises received?}
    K -->|No — restart| A
    K -->|Yes| L[Phase 2a: Determine value v\nuse highest prior accepted value\nor own value if none]
    L --> M[Broadcast Accept n v\nto same quorum]
    M --> N[Acceptor checks:\nn >= promised n?]
    N -->|No| O[Reject Accept]
    N -->|Yes| P[Accept n v\nreply Accepted n v]
    P --> Q{Majority\naccepted?}
    O --> Q
    Q -->|No| A
    Q -->|Yes| R[Value v is CHOSEN]
    R --> S[Notify Learners\nvalue = v]
    S --> T([Consensus reached])

    style R fill:#d1fae5,stroke:#10b981
    style T fill:#d1fae5,stroke:#10b981