Broadcasting multiple messages in simultaneous send/receive systems

Abstract

We investigate the problem of broadcasting multiple messages in a message-passing system that supports simultaneous send and receive. The system consists of n processors, one of which has m messages to broadcast to the other n-1 processors. The processors communicate in rounds. In each round, a processor can simultaneously send a message to one processor and receive a message from another processor. The goal is to broadcast the m messages among the n processors in the minimal number of communication rounds. The lower bound on the number of rounds required is (m-1)+[log n]. We present an algorithm for this problem that requires at most m+[log n] communication rounds, for any values of m and n.