About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Discrete Applied Mathematics
Paper
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.