What is Paxos?

Paxos is a classic consensus algorithm (Leslie Lamport, 1990s). A group of nodes agrees on a single value even if proposers fail and messages are lost. Multi-Paxos extends this to a full replicated log (like Raft’s job).
Examples:
Google Chubby — distributed lock / coordination service (Paxos).
Google Spanner — globally distributed DB; Paxos per shard for replication.
Apache ZooKeeper — uses Zab (Paxos-like) for coordination.
Custom enterprise DBs and locking services needing proven quorum safety.

Roles

Proposer — suggests a value with a proposal number.
Acceptor — votes; remembers the highest proposal it promised to consider.
Learner — learns the chosen value once a quorum accepts it.

How Paxos works (single round)

Phase 1 — Prepare — Proposer sends prepare(n) with proposal number n.
Promise — Acceptors reply: “I will ignore proposals < n” and report any value they already accepted.
Phase 2 — Accept — If proposer gets a majority of promises, it sends accept(n, value).
Chosen — If a majority accept, that value is chosen; Learners are notified.

sequenceDiagram
  participant P as Proposer P1
  participant A1 as Acceptor A
  participant A2 as Acceptor B
  participant A3 as Acceptor C
  participant L as Learner

  P->>A1: prepare(n=5)
  P->>A2: prepare(n=5)
  P->>A3: prepare(n=5)
  A1-->>P: promise(n=5)
  A2-->>P: promise(n=5)
  A3-->>P: promise(n=5)
  Note over P: Majority promised

  P->>A1: accept(n=5, value="leader=X")
  P->>A2: accept(n=5, value="leader=X")
  P->>A3: accept(n=5, value="leader=X")
  A1-->>P: accepted
  A2-->>P: accepted
  A3-->>P: accepted
  Note over P,L: Value chosen — learners apply "leader=X"