The Byzantine generals problem
generals must agree on whether to attack or retreat by exchanging oral (unsigned) messages, and up to of them are traitors who may send arbitrary messages. All loyal generals must reach the same decision, and if the commanding general is loyal they must follow the commander's order. For which and is this possible? In particular, show that 3 generals cannot cope with a single traitor.
History and references
Solved in 1982 by Leslie Lamport, Robert Shostak and Marshall Pease.
Robert Shostak formalized the underlying problem at SRI International around 1978, under the name interactive consistency, in work sponsored by NASA, and Leslie Lamport later recast it as a story about Byzantine generals in a 1982 paper with Shostak and Marshall Pease. They proved that with oral messages agreement is possible exactly when , that is, when more than two thirds of the generals are loyal. With 3 generals and 1 traitor, a loyal lieutenant who receives conflicting reports cannot tell whether the commander or the other lieutenant is lying, because both situations look identical from its point of view. With unforgeable signed messages the problem becomes solvable for any number of traitors. These results are the foundation of Byzantine fault tolerant systems.
References
Solutions 0
Sign in or create an account to publish a solution