The consensus problem in unreliable distributed systems (a brief survey)
Lecture notes in computer sciencePublished 1 January 1983
Michael J. Fischer
Citations359
SJR quartileQ2
SJR score0.35
SNIP0.55
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 considerable literature on this problem that has developed over the past few years is surveyed and an informal overview of the major theoretical results is given.
Abstract
Agreement problems involve a system of processes, some of which may be faulty. A fundamental problem of fault-tolerant distributed computing is for the reliable processes to reach a consensus. We survey the considerable literature on this problem that has developed over the past few years and give an informal overview of the major theoretical results in the area.
Keywords
Computer Science
IEEE Transactions on Information TheoryNew directions in cryptography
14,441 Citations1976Whitfield Diffie, Martin E. Hellman
Communications of the ACMA method for obtaining digital signatures and public-key cryptosystems
13,142 Citations1983Ronald L. Rivest, Adi Shamir +1 more
Communications of the ACMA method for obtaining digital signatures and public-key cryptosystems
13,083 Citations1978Ronald L. Rivest, Adi Shamir +1 more
An encryption method is presented with the novel property that publicly revealing an encryption key does not thereby reveal the corresponding decryption key, soriers or other secure means are not needed to transmit keys.
ACM Transactions on Programming Languages and SystemsThe Byzantine Generals Problem
5,966 Citations1982Leslie Lamport, Robert E. Shostak +1 more
It is shown that, using only oral messages, the problem of a group of generals camped with their troops around an enemy city is solvable if and only if more than two-thirds of the generals are loyal; so a single traitor can confound two loyal generals.
Journal of the ACMReaching Agreement in the Presence of Faults
2,364 Citations1980Marshall C. Pease, Robert E. Shostak +1 more
It is shown that the problem is solvable for, and only for, n ≥ 3m + 1, where m is the number of faulty processors and n is the total number and this weaker assumption can be approximated in practice using cryptographic methods.
Weighted voting for replicated data
1,323 Citations1979David K. Gifford
The algorithm guarantees serial consistency, admits temporary copies in a natural way by the introduction of copies with no votes, and has been implemented in the context of an application system called Violet.
SIAM Journal on ComputingAuthenticated Algorithms for Byzantine Agreement
630 Citations1983Danny Dolev, H. Raymond Strong
This paper presents algorithms for reaching agreement based on authentication that require a total number of messages sent by correctly operating processors that is polynomial in both t and the number of processors, n.
Randomized byzantine generals
575 Citations1983Michael O. Rabin
A randomized solution for the Byzantine Generals Problems that produces Byzantine Agreement within a fixed small expected number of computational rounds, independent of the number n of processes and the bound t on the number of faulty processes.
Another advantage of free choice (Extended Abstract)
566 Citations1983Michael Ben-Or
This work exhibits a probabilistic solution for this problem, which guarantees that as long as a majority of the processes continues to operate, a decision will be made (Theorem 1).
Proceedings of the IEEESIFT: Design and analysis of a fault-tolerant computer for aircraft control
566 Citations1978J. H. Wensley, Leslie Lamport +6 more
SIFT (Software Implemented Fault Tolerance) is an ultrareliable computer for critical aircraft control applications that achieves fault tolerance by the replication of tasks among processing units by using a novel fault-tolerant synchronization method.
Journal of AlgorithmsThe Byzantine generals strike again
565 Citations1982Danny Dolev
The results obtained in the present paper prove that unanimity is achievable in any distributed system if and only if the number of faulty processors in the system is less than one third of the total number of processors and less than half of the connectivity of the system''s network.
Information Processing LettersA lower bound for the time to assure interactive consistency
519 Citations1982Michael J. Fischer, Nancy Lynch
It is shown that any algorithm which assures interactive consistency in the presence of m faulty processors requires at least m + 1 rounds of communication.
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.
Cryptographic protocols
237 Citations1982Richard A. DeMillo, Nancy Lynch +1 more
A cryptographic transformation is a mapping f from a set of cleartext messages, M, to aSet of ciphertext messages, f, so that f(m) should be difficult to infer from f and public knowledge about f.
ACM SIGOPS Operating Systems ReviewLOCUS a network transparent, high reliability distributed system
215 Citations1981Gerald J. Popek, Bruce J. Walker +5 more
Journal of the ACMThe Weak Byzantine Generals Problem
215 Citations1983Leslie Lamport
It is shown that, like the original Byzantine Generals Problem, the weak version can be solved only ff fewer than one-third of the processes may fad and an approximate solution exists that can tolerate arbaranly many failures.
Impossibility of distributed consensus with one faulty process
150 Citations1983Michael J. Fischer, Nancy Lynch +1 more
It is shown that every protocol for this problem has the possibility of nontermination, even with only one faulty process, in the asynchronous consensus problem.
Polynomial algorithms for multiple processor agreement
149 Citations1982Danny Dolev, H. Raymond Strong
It is proved that no matter what kind of information is exchanged, there is no way to reach agreement with fewer than t+1 rounds of exchange, where t is the upper bound on the number of faults.
Information and ControlAn efficient algorithm for byzantine agreement without authentication
149 Citations1982Danny Dolev, Michael J. Fischer +3 more
An explicit solution not using authentication for n = 3t + 1 processes is given, using 2t + 3 rounds and O(t3 log t) message bits.
LOCUS a network transparent, high reliability distributed system
120 Citations1981Gerald J. Popek, Bruce J. Walker +5 more
LOCUS is a distributed operating system that provides a very high degree of network transparency while at the same time supporting high performance and automatic replication of storage and Atomic file operations and extensive synchronization are supported.
Current Pharmaceutical DesignByzantine Generals and Transaction Commit Protocols
107 Citations1982Leslie Lamport, Michael J. Fischer
The current research status on photosensitizing drugs and its correlation to phototoxicity are highlighted and different mechanisms of photodegradation of photolabile drugs have also been discussed.
IEEE Transactions on ComputersSynchronization and Matching in Redundant Systems
78 Citations1978Davies, Wakerly
A novel mutual feedback technique, called "synchronization voting," is introduced that does not have vulnerability to common-point failures and is described in the appendix—a fault-tolerant crystal-controlled clock.
Method for distributed transaction commit and recovery using Byzantine Agreement within clusters of processors
67 Citations1983C. Mohan, Ray Strong +1 more
The present work differs from that presented in [DoSt82b] by increasing the scope (handling a general tree of processes, and multi-cluster transactions) and by providing an explicit set of recovery algorithms.
'Eventual' is earlier than 'immediate'
59 Citations1982Danny Dolev, Ruediger Reischuk +1 more
Two algorithms are presented that in many cases reach the second type of agreement faster than previously known algorithms showing that there actually is a difference between the two notions: Eventual Byzantine Agreement can be reached earlier than Immediate.
Unanimity in an unknown and unreliable environment
58 Citations1981Danny Dolev
It is proved that independently of the model, unanimity is achievable if and only if the number of faulty processors in the system is less than less than one half of the connectivity of the system's network.
A Simple and Efficient Byzantine Generals Algorithm.
53 Citations1982Nancy Lynch, Michael J. Fischer +1 more
An explicit solution is given for a binary value among n=3t+1 processes, using 2t+4 rounds and o(t/sup 3/ log t) message bits, where t bounds the number of faulty processes.
On the minimal synchronism needed for distributed consensus
52 Citations1983Danny Dolev, Cynthia Dwork +1 more
Bounds on information exchange for Byzantine Agreement
45 Citations1982Danny Dolev, Ruediger Reischuk
This paper studies the amount of information exchange necessary to ensure Byzantine Agreement and presents an algorithm that achieves this bound and for which the number of phases does not exceed the minimum t+1 by more than a constant factor.
Lecture notes in computer scienceA new solution for the Byzantine generals problem
20 Citations1983Rüdiger Reischuk
A deterministic algorithm is presented that exhibits early stopping by phase 2f+4 in the worst case, where f is the actual number of faults, under less stringent conditions than the ones of previous algorithms.