This is a solution
27 on the hard interview questions node
. If you have not read the question
, the follow
ing will make no sense
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.