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?

Vishy Venugopalan
Sunday, March 09, 2003

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.

Hill

Henry D. Nissenbaum
Friday, March 14, 2003

Yes, there is a protocol the blue armies can use to avoid defeat:

1) Send battle commands (such as "attack at noon with all forces") to neighbouring blue armies
2) If a command received corresponds exactly with a command that was sent, then execute the command

So, if a commander sends out the order to attack but does not receive the same order, the attack is postponed.

If a commander sends out the order, and the same order is received, the attack goes ahead.

flying lunch boy
Monday, March 17, 2003

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.

If you add an extra acknowledgement message on, then if that gets lost the same thing happens...

Gareth Marshall
Tuesday, March 18, 2003

You are right.

I guess each commander would have to send a command and have acknowledgement, for a total of 4 successfull messages:

Blue 1: "Attack at Noon"
Blue 2: "Acknowledged.  Attack at Noon"
Blue 1: "Acknowledged.  We know you will attack."
Blue 2: "Acknowledged.  We know you know we will attack."

For best results you could send multiple redundant messengers.

flying lunch boy
Tuesday, March 18, 2003

But four messages does not work either -- what if the last one is lost?  Do you attack or not?

Eric

Eric Lippert
Wednesday, April 02, 2003

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?

If so, then the first commander can send his messenger(s), and even if he gets no acknowledgement he could still get ready to attack at noon, but pull out if he doesn't see the other commander moving at the designated hour.

But that seems like too easy an answer, so perhaps the question should really have the blue armies in valleys with the red army at the top of a hill in between.

But I guess the real point of asking the question is to see how long the candidate continues with trying to build a protocol with what ends up being an infinite series of ACKs.

Jonno Downes
Friday, April 04, 2003

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. :-)

David Clayworth
Friday, April 04, 2003

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.

My friend and I want to communicate via email.  Each of our ISP's is blacklisted by the other, and deletes all of the other's incoming mail.  How do we correspond?

Brian
Friday, April 04, 2003

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"?

Matthew
Monday, April 07, 2003

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.

I like this as an interview question because there is a baseline answer (2-phase commit) and becaus you can ask lots of follow-up questions which will show the depth to which the candidate understands it.

David Clayworth
Monday, April 07, 2003

To avoid defeat, the blue armies need not do anything.

Daniel Chong
Tuesday, April 15, 2003

  Recent Topics

  Fog Creek Home