Process cooperation in multiple message broadcast

摘要

We present an optimal algorithm for broadcasting m messages from one process to n - 1 other processes in a one-port fully connected communication model, where m ≥ 1, n > 1. In this algorithm, the processes are organized into 2~([logn]) cooperation units, each consisting of one or two processes. Messages are broadcast among the units following a basic schedule. Processes in each two-process unit cooperate to carry out the basic schedule. At any communication round, either process has at most one message that the other has not received. This algorithm completes the broadcast operation in m + [logn] - 1 communication rounds, which is theoretically optimal. We consider practical issues for efficient implementation of the algorithm and develop a schedule construction that has both time and space complexity of O(logn). Empirical study shows that this algorithm outperforms other widely used algorithms significantly when the data to broadcast is large.