Red Army-Blue Army Problem
Two blue armies are eached poised on opposite hills preparing to attack a single red army in the valley. The red army can defeat either of the blue armies seperately but will fail to defeat both blue armies if they attack simultaneously. The blue armies communicate via an unreliable communications system(a foot soldier). The commander with one of the blue armies would like to attack at noon. His problem is this: If he sends a message to the other blue army, ordering the attack, he cannot be sure it will get through. He could ask for acknowledgement, but that might not get through. Is there a protocol that the blue armies can use to avoid defeat?
No. There is no way each of the blue armies can know what the other knows. In order to attack one will have to assume its message got through.
Henry D. Nissenbaum
Yes, there is a protocol the blue armies can use to avoid defeat:
flying lunch boy
That won't work, unfortunately, if blue one sent the message to blue two and blue two sent a reply that got lost, blue two would attack but not blue one.
You are right.
flying lunch boy
But four messages does not work either -- what if the last one is lost? Do you attack or not?
The way the question is phrased, with the blue armies at the top of hills seperated by a valley, wouldn't they each be able to see whether or not the other army was attacking?
There is a way. Send out the entire army out one by one as messengers. When the last messenger reaches the other army, both armies will be in one place and they can attack together. :-)
I think David Clayworth's solution is the only one possible. Unless I am misinterpreting something, it boils down to trying to set up reliable communication over an arbitrarily unreliable medium. The statement of the problem allows the situation where no messenger ever gets to his destination.
For the programmers who read this board (most of you, I guess), isn't this question the same as "how do I do a 2-phase commit"?
Yep, I think 2-phase commit is where most people started on this. The discussion is mostly because 2-phase commit isn't totally reliable. If I remember there are explicit assumptions that a) eventually two working machines will succeed in exchanging packets b) no machine will be down for ever.
To avoid defeat, the blue armies need not do anything.
Fog Creek Home