Message-optimal protocols for reliable broadcasts in networks with crash failures

We consider reliable broadcast protocols in both weakly synchronous and totally asynchronous distributed systems with point-to-point communication links. We present protocols that, in an n-process system subject to at most t crash failures, guarantees the delivery of a message from any process to other nonfaulty processes. In the absence of failures, our protocols require (n+t-1) messages in the weakly synchronous model and (t+1)(n-1-½) messages in the totally asynchronous model. Moreover, we show that the message complexity of our protocol is optimal