Impossibility of (Repeated) Reliable Broadcast

We consider the problem of Generic Repeated Coordination, of which Reliable Broadcast and Repeated Distributed Consensus are but two instances. We show that in the absence of infinite storage capacity, all problems in this class require perfect failure detectors, highlighting significant assumptions made by many protocols assuming reliable broadcast. Our work also shows that the usual reason used to explain the impossibility of Distributed Consensus in asynchronous systems is misattributed; that is, it is not the inability of a process to know whether a remote process is crashed that makes Consensus impossible. Finally, in the absence of perfect failure detectors, and of processes that never crash, this work illuminates the need for a more flexible notion of "non-faulty process", and for a thorough investigation of coordination problems in which the set of participating processes is dynamic. 1 Introduction Agreement and coordination problems in distributed systems have been researched..