(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 1975 paper is the first published consideration of the problem of consensus in the presence of faults that I know of, 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.
E. A. Akkoyunlu, K. Ekanadham, and R. V. Huber, Some constraints and tradeoffs in the design of network communications, Proc. 5th ACM Symposium on Operating Systems Principles, pages 67-74, 1975.
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 Black.
Entry modified 12 February 2019.
HTML page formatted Wed Mar 13 12:42:45 2019.
Cite this as:
Paul E. Black, "Byzantine generals", in
Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 12 February 2019. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/byzantine.html