ACM SIGACT News Distributed Computing Column 10Sergio Rajsbaum∗AbstractThe Distributed Computing Column covers the theory of systems that are composed of anumber of interacting computing elements. These include problems of communication and net-working, 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 includingin this column, including news and communications, open problems, and authors willing to writea guest column or to review an event related to theory of distributed computing.Deconstructing Paxos1Romain Boichat, Partha DuttaDistributed Programming LaboratorySwiss Federal Institute of TechnologyLausanne, SwitzerlandSvend FrølundHewlett-Packard Labs1501 Page Mill RdPalo Alto, USARachid GuerraouiDistributed Programming LaboratorySwiss Federal Institute of TechnologyLausanne, SwitzerlandAbstractThe celebrated Paxos algorithm of Lamport implements a fault-tolerant deterministic service byreplicating it over a distributed message-passing system. This paper presents a deconstruction ofthe algorithm by factoring out its fundamental algorithmic principles within two abstractions: aneventual leader election and an eventual register abstractions. In short, the leader election abstrac-tion encapsulates the liveness property of Paxos whereas the register abstraction encapsulates itssafety property. Our deconstruction is faithful in that it preserves the resilience and efficiency of theoriginal Paxos algorithm in terms of stable storage logs, message complexity, and communicationsteps. In a companion paper, we show how to use our abstractions to reconstruct powerful variantsof Paxos.∗Instituto de Matem´aticas, UNAM. Ciudad Universitaria, Mexico City, D.F. 04510 [email protected] work is partially supported by the Swiss National Science Foundation (project number 510-207).ACM SIGACT News 47 March 2003 Vol. 34, No. 1The Island of Paxos used to host a great civilisation, which was unfortunately destroyed by aforeign invasion. A famous archaeologist reported on interesting parts of the history of Paxons andparticularly described their sophisticated part-time parliament protocol [15]. Paxos legislators main-tained consistent copies of the parliamentary records, despite their frequent forays from the chambe rand the forgetfulness of their messengers. Although recent studies led to new ways to describe theparliament algorithm [16, 17], as well as powerful tools to reason about its correctness [20], ourdesire to better understand the Paxon civilisation motivated us to revisit the Island and spend sometime deciphering the ancient manuscripts of the legislative system. We discovered that Paxonshad precisely codified various aspects of their parliament protocol within specific sub-protocols: onesub-protocol used to ensure the progress of the parliament and one sub-protocol used to ensure itsconsistency. The precise codification of these sub-protocols helped Paxons adapt their algorithm tovarious seasons of their parliament.1 IntroductionThe Paxos part-time parliament algorithm of Lamport [15] provides a very practical way to im-plement a highly-available deterministic service by replicating it over a system of (non-malicious)processes communicating through message passing. Replicas follow the state-machine pattern, alsocalled active replication [14, 22]. Each replica is supposed to compute every request and return theresult to the corresponding client, which selects the first returned result. Paxos maintains safety(replica consistency) by ensuring total order delivery of requests. It does so even during unstableperiods of the system, e.g., even if messages are delayed or lost and processes crash and recover.Thus, Paxos is indulgent in the sense of [11]. Paxos ensures liveness (result delivery) whenever thesystem stabilizes, and it does so in a very efficient way. Paxos involves however many tricky detailsand it is difficult to factor out the abstractions that comprise the algorithm. Deconstructing Paxosand identifying those abstractions is an appealing objective towards practical implementations ofthe algorithm, as well as effective reconstructions and adaptations of it in specific settings.In [17, 20, 16], Paxos was described as a sequence of consensus instances. The focus was onconsensus which, from a solvability point of view, is indeed equivalent to ensuring total order requestdelivery [6]. However, providing the efficiency of the original Paxos algorithm goes through breakingthe consensus abstraction and combining some of its underlying algorithmic principles with non-trivial techniques such as log piggy-backing and leasing. In particular, this means that the modularcorrectness proof given in [20] does not apply to the actual (optimized) Paxos algorithm. The goalof our paper is to describe a deconstruction of the Paxos that is faithful in that the underlyingabstractions do no need to be broken in order to preserve the efficiency of the original Paxosreplication scheme.The key to our faithful deconstruction is the identification of the new notion of 3Register,which can be implemented with a majority of correct processes in an asynchronous system anddoes not fall within the FLP impossibility of consensus [10]. We use 3Register in conjunction witha 3Leader abstraction, which captures the exact amount of synchrony needed to ensure agreementamong replicas [5]. In short, the leader election abstraction encapsulates the progress procedure ofPaxos that ensures liveness (i.e., service availability), whereas the register abstraction encapsulatesthe state management procedure of Paxos that ensures safety (i.e., consistency of service).Our abstractions are both first class citizens at the level of the replication algorithm. Hence,ACM SIGACT News 48March 2003 Vol. 34, No. 1instead of considering Paxos as a sequence of consensus instances [16, 17, 20], we consider it as asequence of compositions of finer-grained 3Register and 3Leader instances. Our deconstruction ofPaxos is modular, and yet it preserves the resilience and efficiency of the original algorithm in termsof stable storage logs, message complexity and communication steps. In a companion
View Full Document
Unlocking...