The two generals problem
Two armies on opposite hills must attack a city at the same time to win, and an army attacking alone is destroyed. The generals can communicate only by messengers who cross a valley and may be captured. Is there a protocol with a finite number of messages that guarantees the generals always attack together and never alone? Prove your answer.
History and references
Solved in 1975 by E. A. Akkoyunlu, K. Ekanadham and R. V. Huber.
The problem was first published by Akkoyunlu, Ekanadham and Huber in 1975 and was named by Jim Gray in 1978. The answer is no. Suppose a protocol always works, and look at a run in which both generals attack using the fewest messages. The sender of the last message cannot tell whether it arrived, so it attacks either way, and then the receiver must also attack without it, so the protocol works without that message, contradicting minimality. Repeating this removes every message, which is absurd. Real systems therefore accept some uncertainty and use repeated messages, acknowledgements and timeouts to make failure unlikely rather than impossible.
References
Solutions 0
Sign in or create an account to publish a solution