The Part-Time Parliament

Nghị viện Bán thời gian

Leslie Lamport

Bài báo này xuất hiện trong ACM Transactions on Computer Systems 16, 2 (tháng 5 năm 1998), 133-169. Các sửa chữa nhỏ được thực hiện vào ngày 29 tháng 8 năm 2000.

Nghị viện Bán thời gian

LESLIE LAMPORT Digital Equipment Corporation

Những khám phá khảo cổ học gần đây trên đảo Paxos cho thấy nghị viện đã hoạt động bất chấp xu hướng di chuyển liên tục của các nhà lập pháp bán thời gian. Các nhà lập pháp duy trì những bản sao nhất quán của biên bản nghị viện, bất chấp những lần rời khỏi phòng họp thường xuyên của họ và sự đãng trí của các sứ giả. Giao thức của nghị viện Paxon cung cấp một phương pháp mới để triển khai cách tiếp cận máy trạng thái trong việc thiết kế các hệ thống phân tán. Các hạng mục và Bộ mô tả chủ đề: C2.4 [Mạng Truyền thông Máy tính]: Hệ thống phân tán—hệ điều hành mạng; D4.5 [Hệ điều hành]: Độ tin cậy—Khả năng chịu lỗi; J.1 [Xử lý Dữ liệu Hành chính]: Chính phủ Các thuật ngữ chung: Thiết kế, Độ tin cậy Các Từ khóa và Cụm từ bổ sung: Máy trạng thái, cam kết ba pha, bỏ phiếu

Bản gửi này gần đây được phát hiện phía sau một tủ hồ sơ trong văn phòng biên tập TOCS. Mặc dù đã có tuổi đời, tổng biên tập cho rằng nó đáng được xuất bản. Vì tác giả hiện đang tiến hành công việc thực địa tại các đảo Hy Lạp và không thể liên lạc được, tôi được yêu cầu chuẩn bị nó để xuất bản.

Tác giả dường như là một nhà khảo cổ học chỉ có mối quan tâm thoáng qua đến khoa học máy tính. Đây là điều đáng tiếc; mặc dù nền văn minh Paxon cổ đại ít được biết đến mà ông mô tả không mấy được các nhà khoa học máy tính quan tâm, hệ thống lập pháp của nó là một mô hình tuyệt vời cho cách triển khai một hệ thống máy tính phân tán trong một môi trường bất đồng bộ.

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