The Part-Time Parliament

This article appeared in ACM Transactions on Computer Systems 16, 2 (May 1998), 133-169. Minor corrections were made on 29 August 2000.

The Part-Time Parliament

LESLIE LAMPORT Digital Equipment Corporation

Recent archaeological discoveries on the island of Paxos reveal that the parliament functioned despite the peripatetic propensity of its part-time legislators. The legislators maintained consistent copies of the parliamentary record, despite their frequent forays from the chamber and the forgetfulness of their messengers. The Paxon parliament’s protocol provides a new way of implementing the state-machine approach to the design of distributed systems.

Categories and Subject Descriptors: C2.4 [Computer-Communications Networks]: Distributed Systems—Network operating systems; D4.5 [Operating Systems]: Reliability—Fault-tolerance; J.1 [Administrative Data Processing]: Government

General Terms: Design, Reliability

Additional Key Words and Phrases: State machines, three-phase commit, voting

This submission was recently discovered behind a filing cabinet in the TOCS editorial office. Despite its age, the editor-in-chief felt that it was worth publishing. Because the author is currently doing field work in the Greek isles and cannot be reached, I was asked to prepare it for publication.

The author appears to be an archeologist with only a passing interest in computer science. This is unfortunate; even though the obscure ancient Paxon civilization he describes is of little interest to most computer scientists, its legislative system is an excellent model for how to implement a distributed computer system in an asynchronous environment. Indeed, some of the refinements the Paxons made to their protocol appear to be unknown in the systems literature.

The author does give a brief discussion of the Paxon Parliament’s relevance to distributed computing in Section 4. Computer scientists will probably want to read that section first. Even before that, they might want to read the explanation of the algorithm for computer scientists by Lampson [1996]. The algorithm is also described more formally by De Prisco et al. [1997]. I have added further comments on the relation between the ancient protocols and more recent work at the end of Section 4.

Keith Marzullo University of California, San Diego

Authors’ address: Systems Research Center, Digital Equipment Corporation, 130 Lytton Avenue, Palo Alto, CA 94301. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. c 1998 ACM 0000-0000/98/0000-0000 \$00.00

兼职议会

Leslie Lamport

本文发表于《ACM Transactions on Computer Systems》16，2（1998年5月），133-169页。2000年8月29日进行了小幅修正。

兼职议会

LESLIE LAMPORT Digital Equipment Corporation

最近在帕克索斯岛上的考古发现表明，尽管其兼职立法者四处奔波，议会仍然能够正常运作。尽管立法者经常离开议事厅，并且他们的信使经常遗忘信息，他们仍维护了议会记录的一致副本。帕克索斯议会的协议为设计分布式系统时实现状态机方法提供了一种新方式。类别和主题描述：C2.4［计算机通信网络］：分布式系统——网络操作系统；D4.5［操作系统］：可靠性——容错；J.1［行政数据处理］：政府 通用术语：设计，可靠性 其他关键词和短语：状态机，三阶段提交，投票

这篇投稿最近在TOCS编辑部的一个文件柜后面被发现。尽管它年代久远，主编仍认为它值得发表。由于作者目前正在希腊群岛进行实地考察，无法联系到他，我被要求为其出版做准备。

作者似乎是一名考古学家，对计算机科学只有浅显的兴趣。这很遗憾；尽管他所描述的鲜为人知的古代帕克索斯文明对大多数计算机科学家而言并无太大兴趣，但其立法系统是如何在异步环境中实现分布式计算机系统的一个优秀模型。

1 The Problem

This section is missing here.

2 The Single-Decree Synod

This section is missing here.

3 The Multi-Decree Parliament

This section is missing here.

4 Relevance to Computer Science

This section is missing here.

Acknowledgments

This section is missing here.