paper

The Part-Time Parliament

  • Authors:
Read the paper

đŸ“œ Abstract

Recent archaeological discoveries on the island of Paxos reveal that the parliament functioned despite the peripatetic propensity of its part-time legislators. The legislators maintained consistent copies of the parliamentary record, despite their frequent forays from the chamber and the forgetfulness of their messengers. The Paxon parliament’s protocol provides a new way of implementing the state-machine approach to the design of distributed systems.

✨ Summary

Contribution

  • The paper introduces the Paxos consensus algorithm through a parliamentary analogy. Its protocol maintains consistent replicated records despite process failures, delayed or duplicated messages, and legislators repeatedly entering and leaving the chamber. The protocol uses numbered ballots, quorum intersection, and voting rules that preserve consistency while allowing progress when a majority of participants remains available for a sufficiently long period. (microsoft.com)
  • The work connects consensus to the state-machine approach for building fault-tolerant distributed systems and provides a correctness argument for the protocol. (microsoft.com)

Influence

  • Microsoft Research’s publication history states that Paxos was implemented for the Petal distributed system, including dynamic reconfiguration, and was later reused for the Frangipani distributed lock server. (research.microsoft.com)
  • Google researchers reported building a fault-tolerant database using Paxos and documented the engineering issues involved in turning the algorithm into a production-quality system. (research.google)
  • The Chubby paper describes Paxos as a basis for asynchronous consensus and discusses its relationship to highly available distributed services and client libraries. (usenix.org)
  • The Raft paper characterizes Paxos as the dominant consensus algorithm in the preceding decade and states that most consensus implementations were based on or influenced by it; Raft was developed partly in response to difficulties the authors experienced understanding and implementing Paxos. (usenix.org)