The Part-Time Parliament

この論文は ACM Transactions on Computer Systems 16, 2 (May 1998), 133-169 に掲載された。軽微な修正は 29 August 2000 に行われた。

The Part-Time Parliament

LESLIE LAMPORT Digital Equipment Corporation

パクソス島での最近の考古学的発見により、非常勤議員たちがあちこちを移動する傾向にもかかわらず、議会が機能していたことが明らかになった。議員たちは、議場から頻繁に離脱し、また使者たちが忘れっぽかったにもかかわらず、議会記録の一貫したコピーを維持していた。パクソス議会のプロトコルは、分散システムの設計における状態機械アプローチを実装するための新しい方法を提供する。カテゴリおよび主題記述子: C2.4 [Computer-Communications Networks]: 分散システム—ネットワークオペレーティングシステム; D4.5 [Operating Systems]: 信頼性—耐障害性; J.1 [Administrative Data Processing]: 政府 一般用語: 設計、信頼性 追加キーワードおよびフレーズ: 状態機械、三相コミット、投票

この投稿論文は最近、TOCS編集部の書類棚の後ろから発見された。その古さにもかかわらず、編集長は出版する価値があると判断した。著者は現在ギリシャ諸島で現地調査を行っており連絡が取れないため、私は出版の準備を依頼された。

著者は、コンピューター科学にはわずかな関心しか持たない考古学者であるように見える。これは残念なことである。彼が記述する謎めいた古代パクソス文明は、ほとんどのコンピューター科学者にとって興味の対象ではないものの、その立法制度は、非同期環境で分散コンピューターシステムを実装する方法の優れたモデルである。

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

This section is missing here.

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