Deconstructing paxos
- 1 March 2003
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGACT News
- Vol. 34 (1), 47-67
- https://doi.org/10.1145/637437.637447
Abstract
The celebrated Paxos algorithm of Lamport implements a fault-tolerant deterministic service by replicating it over a distributed message-passing system. This paper presents a deconstruction of the algorithm by factoring out its fundamental algorithmic principles within two abstractions: an eventual leader election and an eventual register abstractions. In short, the leader election abstraction encapsulates the liveness property of Paxos whereas the register abstraction encapsulates its safety property. Our deconstruction is faithful in that it preserves the resilience and efficiency of the original Paxos algorithm in terms of stable storage logs, message complexity, and communication steps. In a companion paper, we show how to use our abstractions to reconstruct powerful variants of Paxos.Keywords
This publication has 15 references indexed in Scilit:
- Deconstructing paxosACM SIGACT News, 2003
- ACM SIGACT news distributed computing column 5ACM SIGACT News, 2001
- Failure detection and consensus in the crash-recovery modelDistributed Computing, 2000
- The part-time parliamentACM Transactions on Computer Systems, 1998
- The weakest failure detector for solving consensusJournal of the ACM, 1996
- Unreliable failure detectors for reliable distributed systemsJournal of the ACM, 1996
- Linearizability: a correctness condition for concurrent objectsACM Transactions on Programming Languages and Systems, 1990
- Consensus in the presence of partial synchronyJournal of the ACM, 1988
- Impossibility of distributed consensus with one faulty processJournal of the ACM, 1985
- Time, clocks, and the ordering of events in a distributed systemCommunications of the ACM, 1978