Prove that the two-process coordination problem stated in Section 1.2.5 is impossible to solve.
Let us consider the following message adversary TREE-AD(x), where x ≥ 1 is an integer constant initially known by the processes. TREE-AD(x) is TREE-AD with an additional constraint
limiting its power. Let us remember that G(r) denotes the communication graph on which the
message adversary does not suppress messages during round r.
TREE-AD(x) is such that, for any r, G(r) ∩ G(r + 1) ∩ G(r + x − 1) contains the same
spanning tree. This means that any sequence of x consecutive communication graphs defined by
the adversary contains the same spanning tree. It is easy to see that TREE-AD(1) is TREE-AD.
Moreover, TREE-AD(n − 1) states that the same communication spanning tree (not known by
the processes) exists during the whole computation (made up of (n − 1) rounds).
Does the replacement of the message adversary TREE-AD by the message adversary TREEAD(x) allow the design of a more efficient algorithm?
Solution in [251].