#Number TR-PDS-1996-003 #Title Impossibility of (Repeated) Reliable Broadcast (Revision of TR-PDS-1995-016) #Author Aleta Ricciardi #Abstract We consider the problem of Repeated Reliable Broadcast (RRB) in asynchronous systems, and show that in the absence of infinite storage capacity, solutions to RRB require perfect failure detectors. In the process, we show that the common reason used to explain the impossibility of Distributed Consensus is incorrectly attributed: it is not the inability of a process to know whether a remote process is crashed that makes Consensus impossible. We then generalize the results for RRB to a broad class of problems, which we call Generic Repeated Coordination. We consider some of the implications of our results for protocols that assume reliable broadcast, and show that the need for reliable channels distinguishes Atomic Broadcast from Consensus, which even under weaker channel assumptions, can still be solved with <>W failure detectors. 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''. #Bib