display | more...
This is a solution to problem 27 on the hard interview questions node. If you have not read the question, the following will make no sense to you:

There is no such algorithm. Suppose for contradiction that such an algorithm does exist. Now, consider the shortest run of this algorithm, i.e., a run that requires the fewest number of messages. If the last messenger in the run of the algorithm is captured, then clearly the coordination will not succeed, since then this would not be the shortest run of the algorithm (we might as well have not sent the last messenger).

Since this algorithm fails, we know there is no shortest algorithm, and thus no algorithm exists.

There is no general algorithm if you restrict it to being reliable, but this is an interview question, so it will be followed up by boundary changes.

For example, it's trivial to  prove non-reliable because it is possible for the enemy to capture all 100% of messengers and no coordination can take place.

But if you you allow for multiple messengers to be sent, you could sent n messengers with a message (that includes the number of messengers sent). The return response can send those messengers back. You can judge from the number successful in either direction how good the enemy is at intercepting your messengers, and balance your messenger traffic over time to try to increase the likelihood of your message getting through.

If too many messengers get captured, you don't execute your plan. If enough make it through, you execute. This is even extensible to the case where your messengers may or may not be coerced to change their answer when captured, in which case you can query all messengers sent for a majority answer, and keep going back and forth until you get agreement on your plan, or run out of messengers.

Log in or register to write something here or to contact authors.