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.