Leslie Lamport
Abstract
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.
- BERNSTEIN, P. A., HADZILACOS, V., AND GOODMAN, N. 1987. Concurrency Control and Recovery in Database Systems. Addison-Wesley Longman Publ. Co., Inc., Reading, MA. Google Scholar
- DE PRISCO, R., LAMPSON, B., AND LYNCH, N. 1997. Revisiting the Paxos algorithm. In Proceedings of the 11th International Workshop on Distributed Algorithms, M. Mavronicolas and P. Tsigas, Eds., Lecture Notes in Computer Science, vol. 1320. Springer-Verlag, Berlin, Germany, 111-125. Google Scholar
- DIJKSTRA, E.W. 1974. Self-stabilizing systems in spite of distributed control. Commun. ACM 17, 11, 643-644. Google Scholar
- DWORK, C., LYNCH, N., AND STOCKMEYER, L. 1988. Consensus in the presence of partial synchrony. J. ACM 35, 2 (Apr.), 288-323. Google Scholar
- FEKETE, A., LYNCH, N., AND SHVARTSMAN, A. 1997. Specifying and using a partitionable group communication service. In Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing. ACM Press, New York, NY, 53-62. Google Scholar
- FISCHER, M. J., LYNCH, N. A., AND PATERSON, M. S. 1985. Impossibility of distributed consensus with one faulty process. J. ACM 32, 1 (Jan.), 374-382. Google Scholar
- GRAY, C. AND CHERITON, D. 1989. Leases: An efficient fault-tolerant mechanism for distributed file cache consistency. SIGOPS Oper. Syst. Rev. 23, 5 (Dec. 3-6), 202-210. Google Scholar
- KEIDAR, I. AND DOLEV, D. 1996. Efficient message ordering in dynamic networks. In Proceedings of the 15th Annual ACM Symposium on Principles of Distributed Computing. ACM Press, New York, NY. Google Scholar
- LADIN, R., LISKOV, B., SHRIRA, L., AND GHEMAWAT, S. 1992. Providing high availability using lazy replication. ACM Trans. Comput. Syst. 10, 4 (Nov.), 360-391. Google Scholar
- LAMPORT, L. 1978. Time, clocks, and the ordering of events in a distributed system. Commun. ACM 21, 7, 558-565. Google Scholar
- LAMPORT, L. 1984. Using time instead of timeout for fault-tolerant distributed systems. ACM Trans. Program. Lang. Syst. 6, 2 (Apr.), 254-280. Google Scholar
- LAMPSON, B.W. 1996. How to build a highly available system using consensus. In Distributed Algorithms, O. Babaoglu and K. Marzullo, Eds. Springer Lecture Notes in Computer Science, vol. 1151. Springer-Verlag, Berlin, Germany, 1-17. Google Scholar
- OzI, B. M. AND LISKOV, B.H. 1988. Viewstamped replication: A general primary copy. In Proceedings of the 7th Annual ACM Symposium on Principles of Distributed Computing (Toronto, Ontario, August 15-17, 1988). ACM Press, New York, NY, 8-17. Google Scholar
- SCHNEIDER, F. B. 1990. Implementing fault-tolerant services using the state machine approach: A tutorial. ACM Comput. Surv. 22, 4 (Dec.), 299-319. Google Scholar
- SKEEN, M.D. 1982. Crash recovery in a distributed database system. Ph.D. thesis. University of California at Berkeley, Berkeley, CA.Google Scholar
Index Terms
- The part-time parliament
Recommendations
Members of the Scottish Parliament on the Net
Use of ICT by Members of ParliamentThe creation of the Scottish Parliament in 1999 presented a unique opportunity to integrate new Information and Communication Technologies (ICTs) into a new democratic body. The design of the parliament and democratic practice was informed by the ...
Engineering software assemblies for participatory democracy: the participatory budgeting use case
ICSE '16: Proceedings of the 38th International Conference on Software Engineering CompanionThe worldwide use of the Internet and social networking has transformed the constraints of time and space in human interaction: we can now be heard at a massive scale unprecedented in human history. As a result, information and communication ...
Social Media Use and Political Mobilization
This article describes how political participation is a central component of democracy. Past research has found that a variety of factors drive individual decisions about participation, including the media that citizens use to gain political ...
Reviews
David James Taylor
“`Curiouser and curiouser!' cried Alice,” and the reader of this paper is likely to join Alice in that remark. The first curiosity is that the paper claims to be about an ancient civilization, although readers will rapidly discern that the ancient civilization is a fiction for describing computer algorithms. The second curiosity is that the names used in the examples are given in the Greek alphabet and, when transliterated into the Roman alphabet, turn out to be the names of authors in the reference list. The third curiosity is that the substance of the paper evidently appeared in a 1989 technical report and the paper is shown as having been submitted in 1990, but was not published until 1998. The fourth curiosity, an apparent consequence of the third, is that both the substance of the paper and work derived from it have already appeared in the literature, with the reference list appropriately pointing to such work. The paper itself concerns algorithms for maintaining the consistency of replicated data, using a parliament in which members wander in and out during the proceedings as a means of describing the algorithms. As a tutorial on the behavior of the algorithms, this method of description may be useful. I found the presentation interesting, if curious, but one graduate student who tried to read it could not stand the cuteness and gave up after only a few pages. The algorithms have already been determined to be useful by other researchers, described formally, used as the basis for other algorithms, and so on. The value of this material is thus not in doubt, except for its lack of timeliness.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments