The Two Generals’ Problem is a classic illustration of why reliable coordination over a lossy network is fundamentally hard. Two generals on opposite hills must attack a city at the same time to win, but they can communicate only by sending messengers through the enemy valley, where any messenger may be captured. The puzzle asks whether they can ever become certain they have agreed on a time to attack.
The answer is no. Suppose the first general sends “attack at dawn.” To be sure the order arrived, he needs an acknowledgment. But the second general cannot be sure his acknowledgment arrived, so he needs an acknowledgment of the acknowledgment, and so on. Every message in this chain could be the one that is lost, so no finite number of confirmations ever lets both sides be simultaneously certain. Common knowledge is unattainable over an unreliable channel.
Jim Gray gave the problem its enduring framing as the “two generals paradox” in his influential 1978 lecture notes “Notes on Data Base Operating Systems,” where he used it to explain the limits of coordinating a distributed transaction commit. The underlying impossibility had been described a few years earlier by Akkoyunlu, Ekanadham, and Huber in 1975.
The lesson generalizes far beyond two generals. Because certainty is impossible, real protocols such as two-phase commit and TCP connection handshakes settle for high probability and bounded retries rather than absolute guarantees. The Two Generals’ Problem is the simplest case that exposes this limit, and it is distinct from the Byzantine Generals Problem, which concerns participants who lie rather than a channel that drops messages.