A new solution for the Byzantine generals problem
Information and ControlPublished 1 January 1985
Rüdiger Reischuk
Citations59
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 one 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 + 3 in the worst case, where f is the actual number of faults, under less stringent conditions than the ones of previous algorithms. Its average performance can also easily be analysed making realistic assumptions on random distribution of faults. We show that it stops with high probability after a small number of phases.
Keywords
Computer Science
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.
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 Computer and System SciencesFast probabilistic algorithms for hamiltonian circuits and matchings
586 Citations1979Dana Angluin, Leslie G. Valiant
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.
Journal of the ACMBounds on information exchange for Byzantine agreement
230 Citations1985Danny Dolev, Rüdiger Reischuk
The amount of information exchange necessary to ensure Byzantine Agreement is studied and a lower bound is shown for the number of signatures for any algorithm using authentication and algorithms that achieve this bound are presented.
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.
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.