Consider the model of round by round adversary on two processors. Recall that the Adv can delete one message of the two sent in a round, but may not. Show that if the Adv were forced to delete a message in a round then consensus is solvable, i.e. give an algorithm.
Now the harder part: Show that if the Adv is forced just to eventually delete a message then consensus is still solvable. Your algorithm unlike previously where it “know” that one message will be deleted in the first round, now all the algorithm “knows” is that at some future unknown round a message will be deleted.
We defined the wait-free adversary in the round by round model as deleting at most one message between a pair. For more than 2 processor model, suppose we generalize: The Adv can delete even the 2 messages between a pair as long as the directed graph induced by the messages left is such that for all pi and pj , either pi can reach pj or vice versa, or both. Obviously this is a Generalization. Thus the Former can trivially solve the Latter (as a task). Show that the Latter solves the Former.
(To elaborate: the Former as a task is input to a processor is its id, each pi returns a set Si of processors such that for all pj either pj 2 Si or pi 2 Sj , or both.
The Latter is for each pi and pj there is a sequence pi , pi1 , . . . , pik , pj such that in the sequence if pl is succeeded by pm then pl 2 Sm, or the reverse, or both.)
(Bonus question - very tough, for those who like combinatorics) In the round by round adversary that in each round the Adv deletes at most a single message between a pair. Consider two successive rounds. Prove that there exist a “king” processor - a processor that transitively heard about all other processors. I.e. for pi it either got a message from pi in the first round. If not, then it either received a message from pi in the second round, or it received a message in the second round from pj who in the first round received a message from pi .
A much easier problem is to show that if the Adv behavior in the second round is the same as in the first round, then the above is true.
