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. © 1994.