#Number
TR-PDS-1995-016

#Title 
Impossibility of (Repeated) Reliable Broadcast


#Author
Aleta Ricciardi

#Abstract
We consider the problem of {\em 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 {\em 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.

Keywords: Asynchronous, Coordination, Failure Detectors, Reliable Broadcast
	
#Bib
@InProceedings{,
  author = 	 "Aleta Ricciardi"
  title = 	 "Impossibility of (Repeated) Reliable Broadcast"
  booktitle =	 "",
  address =	 "",
  month =	 "",
  note =	 1995,
  note =	 "available via ftp or WWW at maple.ece.utexas.edu
		  as technical report TR-PDS-1995-016"
}