MESSAGE-OPTIMAL PROTOCOLS FOR FAULT-TOLERANT BROADCASTS MULTICASTS INDISTRIBUTED SYSTEMS WITH CRASH FAILURES/

An essential feature in any fault-tolerant design of distributed syste ms is a mechanism by which a process can reliably broadcast informatio n to other processes in the presence of failures. This paper studies t he message complexity of fault-tolerant broadcast protocols in weakly synchronous and totally asynchronous distributed systems with point-to -point communication links, where the system failures are caused by th e processes but the communication links are completely reliable. We fo cus on the number of messages required of any fault-tolerant protocol in failure-free executions. Our motivation is that one should incur th e cost of handling failures only when they actually occur. We present protocols that, in an n-process system subject to at most t crash fail ures where 1 less than or equal to t < (n - 1), guarantee the delivery of a message from any process to other nonfaulty processes. In the ab sence of crash failures, our protocols require (n + t - 1) messages in the weakly synchronous model and (t + 1)(n - 1 - (t/2)) messages in t he totally asynchronous model. Moreover, we show that in both cases ou r protocols are optimal with respect to message complexity. The new in sights provided in our lower bound proofs also yield graph-theoretic c haracterizations of all message-optimal reliable broadcast protocols i n failure-free executions. Both the upper and lower bound results on b roadcast protocols can be generalized to multicast protocols, where a process only needs to deliver a message to a subset of processes in th e system.