The Part-Time Parliament

SystemExperts

Pricing

Whitepapers

15 items

MapReduce: Simplified Data Processing on Large Clusters

30mintermediate

Kafka: A Distributed Messaging System for Log Processing

30mintermediate

Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services

25mintermediate

Summary

Paxos is the foundational algorithm for achieving consensus in a distributed system where nodes may fail. Presented through an elaborate parable about the parliament of the ancient Greek island of Paxos, the paper describes how legislators who only attended part-time (nodes that may fail) could still pass consistent decrees (agree on values). The algorithm guarantees that if any value is chosen, all nodes that learn a value will learn the same one—even if nodes fail and recover, messages are lost or delayed, and there is no bound on timing. Paxos and its variants underlie virtually all modern distributed systems requiring consensus.

Key Takeaways

Safety Despite Asynchrony

Paxos never violates safety (agreement on a single value) regardless of timing. Messages can be arbitrarily delayed, nodes can fail and recover, and the algorithm still guarantees that once a value is chosen, no other value will ever be chosen. Liveness requires eventual synchrony, but safety is unconditional.

Proposal Numbers as Logical Ordering

Each proposal has a unique number that establishes ordering. Higher-numbered proposals can override lower-numbered ones, but only if the lower-numbered value hasn't been chosen. This mechanism allows progress when leaders fail while preserving any previously chosen values.

Two-Phase Protocol: Prepare and Accept

Phase 1 (Prepare) establishes the right to propose and learns of any previously accepted values. Phase 2 (Accept) proposes a value—either the proposer's choice or a previously accepted value. This two-phase structure ensures that chosen values are never overwritten.

Lamport presents Paxos through an elaborate parable about the ancient Greek island of Paxos, whose parliament had an unusual problem: legislators were merchants and olive traders who couldn't attend full-time. They would wander in and out of the parliamentary chamber, yet the parliament needed to pass consistent decrees.

The constraints: - Legislators could enter or leave the chamber at any time - Messages between legislators could be lost - No central authority to coordinate - Yet every decree ever passed must be recorded consistently

The real problem this models: - Legislators = distributed processes/nodes - Entering/leaving = node failures and recoveries - Lost messages = network unreliability - Passing decrees = achieving consensus on values

The parable, while whimsical, precisely captures the constraints of distributed consensus. The parliament's protocol—later called Paxos—became the foundation of distributed systems theory.

Summary

Key Takeaways

Safety Despite Asynchrony

Proposal Numbers as Logical Ordering

Two-Phase Protocol: Prepare and Accept

Premium Content

Trade-offs

Aspect	Advantage	Disadvantage
Safety vs Liveness Separation	Safety always guaranteed regardless of timing; system never produces wrong answer	Liveness not guaranteed; competing proposers can livelock; needs additional mechanisms
Majority Quorums	Any two majorities overlap, ensuring consistency; simple to reason about	Requires majority availability; can't make progress with exactly half nodes; inflexible
Two-Phase Protocol	Discover any existing chosen values; enable safe preemption; correct despite concurrent proposers	Two round-trips adds latency; Phase 1 can be skipped only with stable leader
No Distinguished Leader	No single point of failure for correctness; any node can propose	Concurrent proposers can conflict; leader optimization needed for performance
Single-Decree Primitive	Clean theoretical foundation; correctness proof is tractable	Gap to practical Multi-Paxos is significant; many details left to implementer

Whitepapers

MapReduce: Simplified Data Processing on Large Clusters

Kafka: A Distributed Messaging System for Log Processing

Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services

Bitcoin: A Peer-to-Peer Electronic Cash System

In Search of an Understandable Consensus Algorithm (Raft)

TAO: Facebook's Distributed Data Store for the Social Graph

The Google File System

The Log-Structured Merge-Tree (LSM-Tree)

The Chubby Lock Service for Loosely-Coupled Distributed Systems

Spanner: Google's Globally Distributed Database

Bigtable: A Distributed Storage System for Structured Data

Scaling Memcache at Facebook

Large-scale cluster management at Google with Borg

The Next 700 Programming Languages