Paxos: The Part-Time Parliament

Historical Context

Leslie Lamport first described Paxos in 1990 using a parable about a fictional Greek parliament on the island of Paxos. The paper was rejected for being too whimsical, so Lamport shelved it. It was finally published in 1998 in ACM Transactions on Computer Systems. Before Paxos, distributed systems lacked a proven, fault-tolerant protocol for reaching agreement among unreliable processes. Two-phase commit existed but could not tolerate coordinator failure. Paxos filled that gap and became the theoretical foundation for nearly every consensus system built since.

Core Problem

How can a group of distributed processes agree on a single value (a log entry, a leader, a configuration change) when any process can crash at any time, messages can be delayed or lost, and there is no shared clock?

Key Innovation

Paxos splits consensus into three roles: Proposers suggest values, Acceptors vote on proposals, and Learners observe the outcome. A proposal succeeds when a majority (quorum) of acceptors agrees, which guarantees that any two quorums overlap by at least one member, preventing conflicting decisions.

The protocol runs in two phases. In Phase 1 (Prepare), a proposer picks a unique, monotonically increasing proposal number and sends a Prepare request to a majority of acceptors. Each acceptor promises not to accept any proposal with a lower number and replies with the highest-numbered proposal it has already accepted, if any. In Phase 2 (Accept), the proposer picks the value from the highest-numbered previously accepted proposal (or its own value if none exists) and sends an Accept request. If a majority accepts, the value is chosen.

This two-phase dance is what makes Paxos safe: even if a proposer crashes mid-protocol, no two different values can both be chosen. Liveness is harder — competing proposers can livelock by continually preempting each other — which is why practical systems elect a distinguished proposer (leader) to drive progress.

Architecture / Algorithm

• Proposal Numbers: Globally unique, monotonically increasing identifiers that impose a total order on proposals.
• Quorums: Any majority subset of acceptors. Overlap between quorums is the key safety property.
• Phase 1 (Prepare/Promise): Establishes a "lease" on a proposal number.
• Phase 2 (Accept/Accepted): Commits a value once a quorum agrees.
• Multi-Paxos: An optimization where Phase 1 is run once for a stable leader, reducing each subsequent consensus round to a single phase.

Strengths

• Provably correct under asynchronous network assumptions
• Tolerates up to F failures with 2F+1 acceptors
• Foundation of virtually all production consensus systems
• Multi-Paxos optimization makes it practical for replicated state machines

Weaknesses

• The original paper is notoriously difficult to understand
• Livelock is possible without leader election
• Performance degrades with many concurrent proposers
• Single-decree Paxos decides only one value; extending to a log (Multi-Paxos) adds complexity that Lamport left under-specified

Modern Systems Influenced

Google Chubby and Spanner use Paxos internally. Apache ZooKeeper's ZAB protocol is a Paxos variant. Raft (used in etcd, Consul, CockroachDB) was designed as an "understandable Paxos." AWS and Azure consensus layers trace back to Paxos ideas.

Interview Relevance

Mention Paxos when discussing leader election, replicated logs, or strong consistency. Know the two-phase structure, why quorum overlap matters, and how Multi-Paxos amortizes overhead. Interviewers value candidates who can explain why majority quorums prevent split-brain rather than just naming the algorithm.

Plain-English Summary

Paxos lets a group of servers agree on one answer even when some servers crash. It works by requiring a majority vote in two rounds: first to lock in a proposal number, then to lock in a value. Because any two majorities share at least one member, conflicting answers cannot both win. Nearly every modern distributed database uses some descendant of Paxos.

Original DosiBridge notes for Paxos: The Part-Time Parliament

This section is written specifically for this page, not copied from a general system-design checklist. The useful way to study Paxos: The Part-Time Parliament is to connect the concept to a production service where growth exposes the first weak assumption in the original design. That framing changes the design discussion from definitions to operating choices.

What makes this topic distinct

• Practice Loop: For Paxos: The Part-Time Parliament, decide the practice loop before choosing tools; otherwise the design looks clean but fails when paxos changes.
• Implementation Exercise: For Paxos: The Part-Time Parliament, decide the implementation exercise before choosing tools; otherwise the design looks clean but fails when paxos changes.
• Review Checkpoint: For Paxos: The Part-Time Parliament, decide the review checkpoint before choosing tools; otherwise the design looks clean but fails when paxos changes.
• Failure Drill: For Paxos: The Part-Time Parliament, decide the failure drill before choosing tools; otherwise the design looks clean but fails when paxos changes.
• Comparison Target: For Paxos: The Part-Time Parliament, decide the comparison target before choosing tools; otherwise the design looks clean but fails when paxos changes.

Production review question

If a team adopts Paxos: The Part-Time Parliament, what observable signal proves it helped instead of only making the architecture diagram more fashionable?

Practical metric to track

Track paxos health as a named dashboard or review item: combine one user-facing metric, one saturation metric, and one correctness metric. For Paxos: The Part-Time Parliament, this keeps the discussion grounded in behavior that can be measured after deployment instead of generic advice that sounds good in an interview but never gets verified.

Sources

• Paxos Made Simple — Lamport, 2001
• The Part-Time Parliament — Lamport, 1998