The Part-Time Parliament

Leslie Lamport, 1998, ACM TOCS

About this paperEnglishTiếng Việt中文beside Englishbeside Tiếng Việtbeside 中文

This paper is under a licence that does not allow it to be reproduced, so what is here is its front matter and a short abstract. Read it at the publisher's page.

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

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

References

  1. Bernstein, P. A., Hadzilacos, V., and Goodman, N. 1987. Concurrency Control and Recovery in Database Systems. Addison-Wesley, Reading, Massachusetts. De Prisco, R., Lampson, B., and Lynch, N. 1997. Revisiting the Paxos algorithm. In
  2. M. Mavronicolas and P. Tsigas (Eds.), Proceedings of the 11th International Workshop on Distributed Algorithms (WDAG 97), Volume 1320 of Lecture Notes in Computer
  3. Science, Saarbruken, Germany, pp. 111–125. Springer-Verlag. Dijkstra, E. W. 1974. Self-stabilizing systems in spite of distributed control. Commun.
  4. ACM 17, 11 (Nov.), 643–644. Dwork, C., Lynch, N., and Stockmeyer, L. 1988. Consensus in the presence of partial synchrony. Journal of the ACM 35, 2 (April), 288–323. Fekete, A., Lynch, N., and Shvartsman, A. 1997. Specifying and using a partitionable group communication service. In Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing, pp. 53–62. ACM Press. Fischer, M. J., Lynch, N., and Paterson, M. S. 1985. Impossibility of distributed consensus with one faulty process. Journal of the ACM 32, 2 (April), 374–382. Gray, C. G. and Cheriton, D. R. 1989. Leases: An efficient fault-toerant mechanism for distributed file cache consistency. In Proceedings of the Twelfth ACM Symposium on Operating Systems Principles, New York, pp. 202–210. ACM. Keidar, I. and Dolev, D. 1996. Efficient message ordering in dynamic networks. In Proceedings of the 15 th Annual ACM Symposium on Principles of Distributed Computing. ACM.
  5. Ladin, R., Liskov, B., Shrira, L., and Ghemawat, S. 1992. Providing high availability using lazy replication. ACM Transactions on Computer Systems 10, 4 (Nov.), 360–391. Lamport, L. 1978. Time, clocks, and the ordering of events in a distributed system. Commun.
  6. ACM 21, 7 (July), 558–565. Lamport, L. 1984. Using time instead of timeout for fault-tolerant distributed systems. ACM
  7. Trans. on Programm. Lang. Syst. 6, 2 (April), 254–280. Lampson, B. W. 1996. How to build a highly available system using consensus. In O. Babaoglu and K. Marzullo (Eds.), Distributed Algorithms, Volume 1151 of Lecture Notes in Computer Science, Berlin, pp. 1–17. Springer-Verlag. Oki, B. M. and Liskov, B. H. 1988. Viewstamped replication: A new primary copy method to support highly-available distributed systems. In Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing, pp. 8–17. ACM Press. Schneider, F. B. 1990. Implementing fault-tolerant services using the state machine approach:
  8. A tutorial. ACM Computing Surveys 22, 4 (Dec.), 299–319. Skeen, M. D. 1982. Crash recovery in a distributed database system. Ph. D. thesis, University of California, Berkeley.
  9. Received January 1990; Accepted March 1998

Read off the page by the text layer of the PDF using pdftotext version 26.09.0. Translated into 日本語 by gpt-5, against glossary version 6. Translated from the English.