(classic problem)
Definition: The problem of reaching a consensus among distributed units if some of them give misleading answers. To be memorable, the problem is couched in terms of generals deciding on a common plan of attack. Some traitorous generals may lie about whether they will support a particular plan and what other generals told them. Exchanging only messages, what decision making algorithm should the generals use to reach a consensus? What percentage of liars can the algorithm tolerate and still correctly determine a consensus?
Note: The problem of consensus in the presence of faults was investigated earlier, but the 1982 paper names the problem.
One variant is: suppose two separated generals will win if both attack at the same time and lose if either attacks alone, but messengers may be captured. If one decides to attack, how can that general be sure that the message has reached the other general and the other general will attack, too?
Author: PEB
Summary of the 1982 paper by Lamport, Shostak, and Pease.
Marshall Pease, Robert Shostak, and Leslie Lamport, Reaching Agreement in the Presence of Faults, Journal of the ACM 27(2): 228-234, 1980.
Leslie Lamport, Robert Shostak and Marshall Pease, The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems, 4(3):382-401, July 1982.
Both available in PDF.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified Thu Sep 8 12:40:39 2005.
HTML page formatted Wed Oct 26 09:47:18 2005.
Cite this as:
Paul E. Black, "Byzantine generals", from
Dictionary of Algorithms and Data
Structures, Paul E. Black, ed.,
NIST.
http://www.nist.gov/dads/HTML/byzantine.html
