Deconstructing paxos
Deconstructing paxos
复制标题
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
R. Boichat;P. Dutta;Svend Frølund;R. Guerraoui
中科院分区：
文献类型：
--
作者：
R. Boichat;P. Dutta;Svend Frølund;R. Guerraoui
分布式计算列涵盖了由许多交互的计算元素组成的系统理论由Romain Boichat，Partha Dutta，SvendFrølund和Rachid Guerraoui组成的“解构Paxos”。 ，包括新闻和通讯，开放问题，以及愿意撰写客人专栏的作者或审查与分布式计算理论有关的事件。惠普 - 帕克德实验室1501 Page Mill Rd Palo Alto，美国Rachid Guerraoui分发了编程实验室瑞士联邦技术研究所洛桑，瑞士摘要Lamport著名的Paxos算法实现了通过分布式的消息 - 填充系统来重复其耐受性的确定性服务。本文通过将其基本算法原理考虑到两个抽象中的基本算法来提出算法的解构：最终的领导者选举和事件登记册的抽象抽象。我们的解构属性是忠实的，因为它保留了原始的Paxos算法的韧性和效率，该算法在稳定的存储日志，消息复杂性和交流步骤方面，我们展示了如何使用抽象来重建强大的Paxos变体。 。最终的登记式抽象。消息和沟通纸工作得到瑞士国家科学基金会的部分支持（项目编号510-207）。一位著名的考古学家报道了Paxon的历史的有趣部分，特别描述了他们精致的兼职议会协议[15]。尽管最近的研究导致了描述议会算法的新方法[16，17]，以及强大的工具来推理其正确性[20]，但我们希望更好地理解Paxon文明的愿望激励我们重新审视该岛并花费一些时间对立法系统的古老手稿解密。 。
The Distributed Computing Column covers the theory of systems that are composed of a number of interacting computing elements. These include problems of communication and networking, databases, distributed shared memory, multiprocessor architectures, operating systems, verification, internet, and the web. This issue consists of the paper “Deconstructing Paxos” by Romain Boichat, Partha Dutta, Svend Frølund, and Rachid Guerraoui. Many thanks to them for contributing to this issue. Request for Collaborations: Please send me any suggestions for material I should be including in this column, including news and communications, open problems, and authors willing to write a guest column or to review an event related to theory of distributed computing. Deconstructing Paxos 1 Romain Boichat, Partha Dutta Distributed Programming Laboratory Swiss Federal Institute of Technology Lausanne, Switzerland Svend Frølund Hewlett-Packard Labs 1501 Page Mill Rd Palo Alto, USA Rachid Guerraoui Distributed Programming Laboratory Swiss Federal Institute of Technology Lausanne, Switzerland 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.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. ∗Instituto de Matemáticas, UNAM. Ciudad Universitaria, Mexico City, D.F. 04510 rajsbaum@math.unam.mx. This work is partially supported by the Swiss National Science Foundation (project number 510-207). ACM SIGACT News 47 March 2003 Vol. 34, No. 1 The Island of Paxos used to host a great civilisation, which was unfortunately destroyed by a foreign invasion. A famous archaeologist reported on interesting parts of the history of Paxons and particularly described their sophisticated part-time parliament protocol [15]. Paxos legislators maintained consistent copies of the parliamentary records, despite their frequent forays from the chamber and the forgetfulness of their messengers. Although recent studies led to new ways to describe the parliament algorithm [16, 17], as well as powerful tools to reason about its correctness [20], our desire to better understand the Paxon civilisation motivated us to revisit the Island and spend some time deciphering the ancient manuscripts of the legislative system. We discovered that Paxons had precisely codified various aspects of their parliament protocol within specific sub-protocols: one sub-protocol used to ensure the progress of the parliament and one sub-protocol used to ensure its consistency. The precise codification of these sub-protocols helped Paxons adapt their algorithm to various seasons of their parliament.