Abstract
Broadcasting is an important operation in many message-passing systems that has been widely investigated. Most existing broadcasting algorithms, however, do not address several emerging trends in distributed-memory parallel computers and high-speed communication networks. These trends include (i) treating the system as being fully connected with all processors equally distant, (ii) packetizing large amounts of data into sequences of messages, and (iii) tolerating communication latencies. In this paper, we explore the broadcasting problem in the postal model that addresses these issues. We provide two efficient algorithms for broadcasting m messages in a fully connected message-passing system with n processors and communication latency λ. A lower bound on the time required for this problem is (m - 1) + fλ(n), where fλ(n) is the optimal time for broadcasting one message. We present two algorithms: The first is Algorithm PARTITION, the running time of which is at most m + n + 2λ when m ≥ n and 3m + fλ(n) + 2λ. when m ≤ n. The second is Algorithm D-D-TREES, the running time of which is at most m + 2fλ(n) + O(λ) for any value of m. © 1997 John Wiley & Sons, Inc.