Reliable Broadcasts Through Partial Broadcasts

Abstract

In the Reliable Broadcast Problem, a processor disseminates a value to all other processors in a distributed system where both processors and communication components are subject to failures. We prove lower bounds for the execution time of any reliable broadcast protocol in distributed systems with arbitrary communication networks. Our results apply to common distributed system architectures consisting of multiple broadcast network-based clusters of processors. In light of these lower bounds, our earlier protocols are shown to be optimal with respect to execution time.