A new solution for the Byzantine generals problem
Lecture notes in computer sciencePublished 1 January 1983
Rüdiger Reischuk
Citations20
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
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.
Abstract
We define a new model for algorithms to reach Byzantine Agreement. It allows to measure the complexity more accurately, to differentiate between processor faults and to include communication link failures. 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. Also its average performance can easily be analysed making realistic assumptions on random distributions of faults. We show that it stops with high probability after a small number of phases.
Keywords
Computer Science
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.
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.
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.
Journal of the ACMSynchronizing clocks in the presence of faults
543 Citations1985Leslie Lamport, P. M. Melliar‐Smith
Three algorithms for maintaining clock synchrony in a distributed multiprocess system where each process has its own clock work in the presence of arbitrary clock or process failures, including “two-faced clocks” that present different values to different processes.
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.
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.
'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.
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.