I’ve been doing some research and reading on the Two Generals’ Problem or Coordinated Attack Problem, the Consensus Problem, etc and it appears to be unsolvable, here’s a simple proof:
Four-Star General = 4G and also the “decider”, in our case. Three-Star General = 3G.
- The Four-Star General decides to attack the fortress.
- He sends a messenger with the “attack at noon” message to the 3G.
- The 3G gets the “attack at noon” message”. At this point the 3G knows that the 4G decided on “attack at noon”, but of course the 4G doesn’t know that the 3G got the message. The 3G can’t safely proceed until he knows that the 4G knows he received the message.
- The 3G sends a messenger back to the 4G to let him know that he received the message (ack, or acknowledged). The 4G doesn’t want to act unless he knows the 3G got the message, so he waits for the ack.
- The 4G gets the acknowledgment. At this point the 4G knows that the 3G got the “attack at noon” message. Unfortunately the 3G doesn’t know whether the 4G got the acknowledgment. The 3G can’t safely start to carry out the plan unless he knows the 4G got the acknowledgment and will carry out his part of the heist, so the 3G must wait for an acknowledgment of his ack.
- The 4G can send an ack for the ack to assure the 3G but …
- The ack’ing and re-ack’ing of ack’s happens ad infinitum.
So clearly, we’ll need some exotic methods so solve the bidirectional Coordinated Attack Problem…
First, we have the infinite time Turing machine, which is a variation of the Zeno machine. The infinite time TM can solve an infinite-step problem in a finite amount of steps. An unbound-time problem like the Two Generals’ can be solved in bound-time. Far fetched? Not as much as you might think 🙂
The second solution is probably a more realistic one: quantum entanglement.
Quantum entanglement, also called the quantum non-local connection, is a property of the quantum mechanical state of a system containing two or more objects, where the objects that make up the system are linked in a way that one cannot adequately describe the quantum state of a constituent of the system without full mention of its counterparts, even if the individual objects are spatially separated.
In a actuality, however, a quantum transfer protocol would no longer be a strictly “bidirectional” protocol; if that’s the case, maybe quantum entanglement is cheating.