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.