Two Generals' Problem
In computing, the Two Generals' Problem is a thought experiment meant to illustrate the pitfalls and design challenges of attempting to coordinate an action by communicating over an unreliable link.
The experiment asks how they might reach an agreement on the time to launch an attack, while knowing that any messenger they send could be captured.
A key concept in epistemic logic, this problem highlights the importance of common knowledge.
[citation needed] The first general may start by sending a message: "Attack at 0900 on August 4."
Thus, it quickly becomes evident that no matter how many rounds of confirmation are made, there is no way to guarantee the second requirement that each general is sure the other has agreed to the attack plan.
[6] Because this protocol is deterministic, suppose there is a sequence of a fixed number of messages, one or more successfully delivered and one or more not.
A protocol that terminates before sending any messages is represented by a tree containing only a root node.
Then, by a similar argument to the one used for fixed-length deterministic protocols above, P' must also solve the Two Generals' Problem, where the tree representing P' is obtained from that for P by removing all leaf nodes and the edges leading to them.
To save them from sacrificing hundreds of lives to achieve very high confidence in coordination, the generals could agree to use the absence of messengers as an indication that the general who began the transaction has received at least one confirmation and has promised to attack.
Suppose it takes a messenger 1 minute to cross the danger zone, allowing 200 minutes of silence to occur after confirmations have been received will allow us to achieve extremely high confidence while not sacrificing messenger lives.
This problem was given the name the Two Generals Paradox by Jim Gray[8] in 1978 in "Notes on Data Base Operating Systems"[9] starting on page 465.
This reference is widely given as a source for the definition of the problem and the impossibility proof, though both were published previously as mentioned above.
