I recall we had this problem in one of my electrical engineering courses, studying packet communications between computers. Unfortunately, I’ve forgotten the answer and it’s driven me nuts for years. If anyone knows, email me.
You have 2 armies, on opposite hilltops. They are allied against an enemy army in the valley between them. Sometimes the 2 armies send runners to send messages to each other. The runners sometimes get killed–say, 1% of the time. So you can’t be 100% sure a message makes it to the recipient.
Now say they 2 armies can defeat the enemy if they attack togehter, but if attacking alone, eihter one will lose. Army 1 wants to attack at sunrise. So they send a runner to 2. But the dilemma is, Army 1 needs to get a message back knowing Army 2 got the message and will attack too. Army 1 can’t assume 2 gets the message since the runner might be killed.
Now Army 2, even if it gets the first message, and wants to attack, wants to be sure 1 got the reply, so 2 does not attack alone.
The question was: is it possible to arrange a communication scheme, given a less than 100% chance of message success, so that they can both attack?
It seems to me NO, but I wonder. It seems to me that to attack you have to have 100% certainty your message made it, and so does the other guy. This must be impossible. You can have an arbitrarily high confidence if you do enough handshaking, I suppose, but you can never be sure. Anyone know if I’m right?
