On General Results For All-To-All Broadcast

All-to-all broadcast refers to the process by which every node broadcasts its certain piece of information to all other nodes in the system. In this paper, we develop all-to-all broadcast schemes by dealing with two classes of schemes. A prior scheme based on generation of minimal complete sets is first described, and then a new scheme based on propagation of experts is developed. The former always completes the broadcasting in the minimal number of steps and the latter is designed to minimize the number of messages. Performance of these two classes of schemes is comparatively analyzed. The all-to-all broadcast scheme desired can be derived by combining the advantages of these two classes of schemes. Index Terms: All-to-all broadcast, message passing, NODUP, expert propagation, communication steps. 1 Introduction Instead of using a shared memory and a global clock, the synchronization and communication between the processing nodes in a distributed system can be done via message pass..