Deconstructing paxos

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.

REFERENCES

• 1: Marcos Kawazoe Aguilera , Wei Chen , Sam Toueg, Failure detection and consensus in the crash-recovery model, Distributed Computing, v.13 n.2, p.99-125, April 2000 [doi>10.1007/s004460050070]
• 2: R. Boichat, P. Dutta, S. Frølund, and R. Guerraoui. Deconstructing Paxos. DSC Technical Report 2001--06, Department of Communication Systems, Swiss Federal Institute of Technology, Lausanne, January 2001.
• 3: Romain Boichat , Partha Dutta , Svend Frølund , Rachid Guerraoui, Deconstructing paxos, ACM SIGACT News, v.34 n.1, March 2003 [doi>10.1145/637437.637447]
• 4: Miguel Castro , Barbara Liskov, Practical Byzantine fault tolerance, Proceedings of the third symposium on Operating systems design and implementation, p.173-186, February 1999, New Orleans, Louisiana, United States
• 5: Tushar Deepak Chandra , Vassos Hadzilacos , Sam Toueg, The weakest failure detector for solving consensus, Journal of the ACM (JACM), v.43 n.4, p.685-722, July 1996 [doi>10.1145/234533.234549]
• 6: Tushar Deepak Chandra , Sam Toueg, Unreliable failure detectors for reliable distributed systems, Journal of the ACM (JACM), v.43 n.2, p.225-267, March 1996 [doi>10.1145/226643.226647]
• 7: Gregory Chockler , Dahlia Malkhi, Active disk paxos with infinitely many processes, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571837]
• 8: Partha Dutta , Svend Frølund , Rachid Guerraoui , Bastian Pochon, An Efficient Universal Construction for Message-Passing Systems, Proceedings of the 16th International Conference on Distributed Computing, p.133-147, October 28-30, 2002
• 9: Cynthia Dwork , Nancy Lynch , Larry Stockmeyer, Consensus in the presence of partial synchrony, Journal of the ACM (JACM), v.35 n.2, p.288-323, April 1988 [doi>10.1145/42282.42283]
• 10: Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
• 11: Rachid Guerraoui, Indulgent algorithms (preliminary version), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.289-297, July 16-19, 2000, Portland, Oregon, United States [doi>10.1145/343477.343630]
• 12: Vassos Hadzilacos , Sam Toueg, Fault-tolerant broadcasts and related problems, Distributed systems (2nd Ed.), ACM Press/Addison-Wesley Publishing Co., New York, NY, 1993
• 13: Maurice P. Herlihy , Jeannette M. Wing, Linearizability: a correctness condition for concurrent objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.463-492, July 1990 [doi>10.1145/78969.78972]
• 14: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 15: Leslie Lamport, The part-time parliament, ACM Transactions on Computer Systems (TOCS), v.16 n.2, p.133-169, May 1998 [doi>10.1145/279227.279229]
• 16: Sergio Rajsbaum, ACM SIGACT news distributed computing column 5, ACM SIGACT News, v.32 n.4, December 2001 [doi>10.1145/568425.568433]
• 17: Butler W. Lampson, How to Build a Highly Available System Using Consensus, Proceedings of the 10th International Workshop on Distributed Algorithms, p.1-17, October 09-11, 1996
• 18: Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 19: Brian M. Oki , Barbara H. Liskov, Viewstamped replication: a general primary copy, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.8-17, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62549]
• 20: Roberto De Prisco , Butler Lampson , Nancy Lynch, Revisiting the PAXOS algorithm, Theoretical Computer Science, v.243 n.1-2, p.35-91, July 28, 2000 [doi>10.1016/S0304-3975(00)00042-6]
• 21: Laura S. Sabel , Keith Marzullo, Election Vs. Consensus in Asynchronous Systems, Cornell University, Ithaca, NY, 1995
• 22: Fred B. Schneider, Replication management using the state-machine approach, Distributed systems (2nd Ed.), ACM Press/Addison-Wesley Publishing Co., New York, NY, 1993
• 23: Jiong Yang , Gil Neiger , Eli Gafni, Structured derivations of consensus algorithms for failure detectors, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.297-306, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277697.277755]