A Simple and Efficient Byzantine Generals Algorithm.
Abstract
The Byzantine Generals problem involves a system of N processes, t of which may be unreliable. The problem is for the reliable processes to agree on a binary value sent by a general, which may itself be one of the N processes. If the general sends the same value to each process, then all reliable processes must agree on that value, but in any case, they must agree on the same value. We give an explicit solution for N=3t+1 processes, using 2t+4 rounds and 0(t-cubed log t) message bits, where t bounds the number of faulty processes. This solution is easily extended to the general case of N > or = 3t+1 to give a solution using 2t+5 rounds and 0(tN+T-cubed log t) message bits. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1982
- Accession Number
- ADA113241
Entities
People
- Michael J. Fischer
- Nancy Lynch
- Robert Fowler
Organizations
- Georgia Tech