Paxos Overview

Overview

Paxos is the original family of consensus protocols. Basic Paxos decides one value; Multi-Paxos chains many decisions into a replicated log. Most modern consensus systems are Paxos relatives, and Raft was designed as a more approachable alternative.

How it works

Three roles exist, often colocated on each node: proposers, acceptors and learners. Each proposal has a unique, increasing number n.

Phase 1  Proposer -> Acceptors: prepare(n)
         Acceptor: if n > promised then promised=n,
                   reply promise(acceptedN, acceptedV)
Phase 2  Proposer -> Acceptors: accept(n, v)
         v = value with highest acceptedN seen, else own value
         Acceptor: if n >= promised then accept
Chosen when a majority accepted the same (n, v)

The key safety rule is that a proposer must adopt any value a majority might already have accepted. Two majorities always overlap in at least one acceptor, so that acceptor carries the earlier decision forward. Multi-Paxos lets a distinguished leader run phase 1 once and then issue only phase 2 messages for each log slot.

Pitfalls

• Acceptors must persist promised and accepted state durably before replying.
• Without a distinguished proposer, rivals keep preempting each other and no value is chosen.
• Gaps in the log need no-op filling after leader change.
• Reconfiguration is outside basic Paxos and easy to get wrong.
• Implementing from papers alone usually yields bugs; prefer a tested library or TLA+ model checking.

Key takeaways

• Paxos guarantees safety always and liveness only with a stable leader.
• Quorum intersection is the core idea behind its correctness.
• Prefer Raft or a vetted library unless you need Paxos-specific variants.