Paxos (computer science)

Paxos (computer science)
Name	Paxos
Caption	Formalization of consensus
Developer	Leslie Lamport
Initial release	1989
Status	Active

Paxos (computer science) is a family of consensus algorithms for achieving agreement among distributed processes or machines in unreliable asynchronous networks. Originally described by Leslie Lamport, Paxos provides a protocol for reaching consensus on a single value and is the basis for many practical systems for replication, coordination, and fault tolerance. Paxos has influenced research and production systems across academia and industry, intersecting with work by researchers and projects at institutions such as Massachusetts Institute of Technology, Stanford University, University of California, Berkeley, Carnegie Mellon University and companies like Google, Amazon (company), Microsoft, Facebook, and Netflix.

Overview

Paxos defines roles—proposers, acceptors, learners—and a sequence of message exchanges to propose and accept values despite failures and message delays. It assumes processes may crash but not act maliciously, similar in assumptions to the models used by Lamport's Paxos originator at Digital Equipment Corporation research and later refined in venues such as ACM SIGACT, IEEE Symposium on Foundations of Computer Science, and ACM Symposium on Principles of Distributed Computing. Paxos addresses the consensus problem formalized earlier by researchers at Princeton University and in the context of the Byzantine Generals Problem comparisons, though Paxos targets crash-fault tolerance rather than Byzantine faults. The algorithm underpins replicated state machines in systems inspired by work from Berkeley DB, Chubby lock service, ZooKeeper, etcd, Consul, Raft-influenced designs and cloud services at Amazon Web Services and Google Cloud Platform.

Algorithm and Variants

The canonical Paxos algorithm consists of Phase 1 (prepare/promise) and Phase 2 (accept/accepted) with proposal numbers to ensure safety; roles map to processes in implementations like Apache ZooKeeper and Microsoft Azure replication. Variants include Multi-Paxos for repeated consensus on sequences of commands, Fast Paxos for reduced latency inspired by Leslie Lamport’s optimizations, Cheap Paxos for minimizing required replicas in failure-free cases, and Byzantine Paxos extensions addressing adversarial faults akin to work by Miguel Castro and Barbara Liskov on Practical Byzantine Fault Tolerance. Other derivatives such as EPaxos, Viewstamped Replication (originally by Brian Oki and Barbara Liskov), and Raft provide alternative trade-offs; EPaxos targets commutative commands as explored at Stanford University and Cornell University. Paxos has been formalized in specification languages like TLA+ developed by Leslie Lamport and model-checked using tools from MIT and INRIA research groups.

Correctness and Safety Properties

Paxos guarantees safety properties including agreement (no two learners decide different values) and validity (decided value was proposed) under asynchronous conditions and crash failures, similar in scope to the FLP impossibility results discussed by Fischer, Lynch and Paterson at Cornell University. Liveness requires additional assumptions such as eventual synchrony or the presence of a stable leader as used in Multi-Paxos and in leader election protocols from Hewlett-Packard and Sun Microsystems literature. Formal proofs and mechanized verifications exist in theorem provers and model checkers developed at Microsoft Research, University of Cambridge, ETH Zurich, and University of Oxford, while counterexamples and pathological executions have been analyzed in workshops and conferences like USENIX Annual Technical Conference and International Conference on Distributed Computing Systems.

Performance and Practical Considerations

Paxos performance depends on message latency, quorum sizes, and leader stability; Multi-Paxos amortizes leader election costs for throughput, an idea used in production systems including Google Spanner and Amazon DynamoDB derivatives. Fast Paxos lowers commit latency at the cost of larger quorums, echoing trade-offs studied at IBM Research and in papers presented at ACM SIGCOMM and USENIX Symposium on Networked Systems Design and Implementation. Implementation choices—persistent storage for acceptor state, batching, read-only leases, and snapshotting—impact recovery and durability in environments from OpenStack deployments to enterprise clusters at Oracle Corporation. Practical tuning often leverages consensus service patterns from Netflix and LinkedIn engineering blogs, while testing uses failure injection frameworks developed at Facebook and Twitter research groups.

Implementations and Applications

Implementations span open-source projects and proprietary systems: Apache ZooKeeper, etcd, Consul (software), Chubby (Google), Google Spanner, RethinkDB, OpenReplica, Berkeley DB, and many databases and coordination services at Amazon Web Services, Microsoft Azure, Alibaba Group, Spotify, Uber Technologies, and Airbnb. Paxos-based coordination is employed for distributed locking, leader election, metadata management, configuration storage, and database replication in systems built by teams at Facebook, Twitter, Dropbox, and Salesforce. Academic and industrial implementations have been evaluated in experiments reported at conferences such as USENIX FAST, VLDB, SIGMOD, and ICDE.

Historical Context and Related Work

Paxos emerged from Leslie Lamport’s theoretical work in the late 1980s and early 1990s and is situated among foundational contributions to distributed computing like the FLP impossibility result from Eugene W. Dijkstra’s contemporaries and the Byzantine fault tolerance literature by Leslie Lamport, Robert Shostak, and Marshall Pease. Related protocols include Lamport’s own refinements, Viewstamped Replication by researchers at Digital Equipment Corporation and DEC Systems Research Center, the Raft algorithm developed by researchers at University of California, Berkeley and Stanford University, and Byzantine-tolerant variants influenced by Miguel Castro and Barbara Liskov. Paxos’s influence extends to standards and industry practices, shaping designs at IETF-related working groups and motivating verification efforts in formal methods communities at INRIA, University of Cambridge, Carnegie Mellon University, and MIT.

Category:Distributed algorithms