The part-time parliament
ACM Transactions on Computer SystemsPublished 1 May 1998Open access
Leslie Lamport
Citations2,714
SJR quartileQ2
SJR score0.63
SNIP1.53
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The Paxon parliament's protocol provides a new way of implementing the state machine approach to the design of distributed systems.
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.
Keywords
Computer Science
Communications of the ACMTime, clocks, and the ordering of events in a distributed system
8,437 Citations1978Leslie Lamport
A distributed algorithm is given for synchronizing a system of logical clocks which can be used to totally order the events, and a bound is derived on how far out of synchrony the clocks can become.
Journal of the ACMImpossibility of distributed consensus with one faulty process
4,554 Citations1985Michael J. Fischer, Nancy Lynch +1 more
In this paper, it is shown that every protocol for this problem has the possibility of nontermination, even with only one faulty process.
Concurrency Control and Recovery in Database Systems
4,310 Citations1987Philip A. Bernstein, Vassco Hadzilacos +1 more
ACM Computing SurveysImplementing fault-tolerant services using the state machine approach: a tutorial
2,379 Citations1990Fred B. Schneider
The state machine approach is a general method for implementing fault-tolerant services in distributed systems and protocols for two different failure models—Byzantine and fail stop are described.
Communications of the ACMSelf-stabilizing systems in spite of distributed control
2,098 Citations1974Edsger W. Dijkstra
The synchronization task between loosely coupled cyclic sequential processes (as can be distinguished in, for instance, operating systems) can be viewed as keeping the relation “the system is in a legitimate state” invariant.
Journal of the ACMConsensus in the presence of partial synchrony
1,873 Citations1988Cynthia Dwork, Nancy Lynch +1 more
Fault-tolerant consensus protocols are given for various cases of partial synchrony and various fault models that allow partially synchronous processors to reach some approximately common notion of time.
Leases: an efficient fault-tolerant mechanism for distributed file cache consistency
484 Citations1989Cary Gray, David R. Cheriton
ACM Transactions on Computer SystemsProviding high availability using lazy replication
386 Citations1992Rivka Ladin, Barbara Liskov +2 more
This paper describes a new way of implementing causal operations that performs well in terms of response time, operation-processing capacity, amount of stored state, and number and size of messages; it does better than replication methods based on reliable multicast techniques.
Viewstamped replication: a general primary copy
375 Citations1988Brian Oki, Barbara Liskov
This paper presents a new replication algorithm that has desirable performance properties, based on the primary copy technique, and uses a special kind of timestamp called a viewstamp to detect lost information.
ACM Transactions on Programming Languages and SystemsUsing Time Instead of Timeout for Fault-Tolerant Distributed Systems.
334 Citations1984Leslie Lamport
Description d'une methode generale pour implementer un systeme reparti ayant n'importe quel degre desire de tolerance de panne, d'un solution au probleme «Bizantine Generals» sont assumes.
Lecture notes in computer scienceHow to build a highly available system using consensus
138 Citations1996Butler Lampson
The general scheme for efficient highly available computing is explained, a general method for understanding concurrent and fault-tolerant programs is given, and the Paxos algorithm is derived as an example of the method.
ACM Transactions on Computer SystemsSpecifying and using a partitionable group communication service
93 Citations2001Alan Fekete, Nancy Lynch +1 more
ACM SIGOPS Operating Systems ReviewLeases: an efficient fault-tolerant mechanism for distributed file cache consistency
72 Citations1989Cary Gray, David R. Cheriton
An analytic model and an evaluation for file access in the V system show that leases of short duration provide good performance and the impact of leases on performance grows more significant in systems of larger scale and higher processor performance.
Efficient message ordering in dynamic networks
69 Citations1996Idit Keidar, Danny Dolev
The aJgorithm always allows processors to initiate messages, even when they are not members of a connected majority component in the network, so that messages can eventually become totally ordered even if their initiator is never a member of a majority component.
Specifying and using a partitionable group communication service
67 Citations1997Alan Fekete, Nancy Lynch +1 more
This paper presents a new, succinct specification for a view-oriented partitionable group communication service, and shows the utility of the specification by constructing an ordered-broadcast application, using an algorithm that reconciles information derived from different instantiations of the group.
Lecture notes in computer scienceRevisiting the Paxos algorithm
66 Citations1997Roberto De Prisco, Butler Lampson +1 more