Process cooperation in multiple message broadcast

✍ Scribed by Bin Jia

• Publisher: Elsevier Science
• Year: 2009
• Tongue: English
• Weight: 475 KB
• Volume: 35
• Category: Article
• ISSN: 0167-8191
• DOI: 10.1016/j.parco.2009.09.002

✦ Synopsis

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 P 1; n > 1. In this algorithm, the processes are organized into 2 blog nc 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 þ dlog ne À 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ðlog nÞ. Empirical study shows that this algorithm outperforms other widely used algorithms significantly when the data to broadcast is large.