A Simple and Efficient Byzantine Generals Algorithm.
Nancy Ann Lynch, Michael J. Fischer, Robert J. Fowler · 1982
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 a binary value among N = 3t + 1 processes, using 2t + 4 rounds and O(t 3 log t) message bits, where t bounds the number of faulty .')rocesses. This solution is easily extended to the genera[ case of N _ 3t + 1 to give a solution using 2t + 5 rounds and O(tN + t31og t) message bits, *This work was supported in part by the Office of Naval Research under Contract N00014.80-C-0221 through a subcontract from the University of Washington, by the Office of Army Research under Contract DAAG29-79-C-0155, and by the National Science Foundation under Grants MCS-79-24370, MCS80-04111, and MCS81-16678. MCS-79-24370, MCS60-04t 11, and MCS81-16678, 1.