Broadcasting Multiple Messages in the Multiport Model.
AbstractWe consider the problem of broadcasting multiple messages from one processor to many processors in the $k$-port model for message-passing systems. In such systems, processors communicate in rounds, where in every round, each processor can send $k$ messages to $k$ processors and receive $k$ messages from $k$ processors. In this paper, we first present a simple and practical algorithm based on variations of $k$ complete $k$-ary trees. We then present an optimal algorithm up to an additive term of one for this problem for any number of processors, any number of messages, and any value for $k$.
Introduction
This paper explores the broadcast problem in the multiport model for message-passing systems.
In particular, we consider (one-to-all) broadcast problem on a message-passing system modeled
by a complete graph of n nodes with k-port model. We assume that there are n processors
(nodes) in the system, denoted by 0; the source of the broadcast (the
broadcaster) is processor 0. We also assume that the source has m messages, denoted by
to broadcast to all the other processors. In the k-port model, each of the
n processors has k distinct input ports and k distinct output ports. In each communication
round, every processor can send k distinct messages to k other processors, and in the same
round each processor can receive k distinct messages that were sent out from k other processors.
Broadcasting is an important communication operation in many multiprocessor systems.
Application domains that use this operation extensively include scientific computations, net-work
management protocols, database transactions, and multimedia applications. Due to the
significance of this operation it is important to design efficient algorithms for it. The broadcasting
operation is frequently used in many applications for message-passing systems (see [11]).
Several collective communication libraries, such as Express [9] by Parasoft and the Message
Passing Library (MPL) [1, 2] of IBM SP2 parallel systems, provide the broadcast primitive.
This operation has also been included as part of the collective communication routines in the
Message-Passing Interface (MPI) standard proposal [8].
Several variations of the broadcasting problem were studied in the literature. (See [13] for a
comprehensive survey.) Most of this research focused on designing broadcasting algorithms for
specific network topologies such as rings, trees, meshes, and hypercubes. However, an emerging
trend in many communication systems is to treat the system as a fully-connected collection
of processors in which every pair of processors can communicate directly. This trend can be
identified in a number of modern multiprocessor systems, such as IBM's Vulcan [17], Thinking
Machines' CM-5 [15], NCUBE's nCUBE/2 [16], Intel's Paragon [12], and IBM's SP2, as well
as in some high-speed communication networks (e.g. PARIS [6]).
When communicating large amounts of data, many systems break the data into sequences of
messages (or packets) that are sent and received individually. This approach motivates research
into the problem of how to disseminate multiple messages efficiently in such systems. Here,
we focus on the problem of broadcasting multiple messages from one source. (Broadcasting a
single message in our model is a simpler task.)
The problem of broadcasting multiple messages in fully-connected systems was studied in
several communication models. Cockayne and Thomason [7] and Farley [10] presented optimal-
time solutions for this problem in a model in which each processor can either send one message
or receive one message in any communication round, but not both. (This model is sometimes
referred to as the unidirectional telephone model or the telegraph model.) In this model, the
optimal number of rounds for odd n is and the optimal number of rounds
for even n is 2m
ne
. In the bidirectional telephone model, Bar-Noy,
Kipnis, and Schieber [5] provided an optimal algorithm that requires (m ne rounds
for even n. For odd n, they presented an algorithm that is optimal up to an additive term of
1 and requires
rounds. They also solved the broadcasting problem
optimally in the simultaneous send/receive model. In this model, in every round, each processor
can send a message to one processor and receive a message from another. (Note that the
send/receive model is equivalent to the 1-port model.) Their solution requires ne
rounds. Bar-Noy and Kipnis [3, 4] as well as Karp et al. [14] also investigated the problem of
broadcasting multiple messages in the Postal and LogP models of communication. In these
models, each processor can simultaneously send one message and receive another message, but
message delivery involves some communication latency. In these models, no optimal solutions
for the problem of broadcasting multiple messages are known for nontrivial values of the
communication latency.
The multiport model generalizes the one-port model that has been widely investigated.
There are examples of parallel systems with k-port capabilities for k ? 1, such as the nCUBE/2
[16], the CM-2 (where k is the dimension of the hypercube in both machines) and transputer-based
machines.
Our results: In this paper we present two algorithms for broadcasting m messages within
an n-node complete graph in the k-port model for any n and any k - 2. The first algorithm,
called the k-tree algorithm, is very simple and practical. It has a time complexity of dm=ke
compared to a simple lower bound of dm=ke
log
\Upsilon
\Gamma 1. Thus,
the delay of each message is optimal up to a small multiplicative factor of log(k
The second algorithm, called the rotation algorithm, is optimal up to an additive term of one.
Specifically, our algorithm requires dm=ke
log
\Upsilon
rounds. The second algorithm is more
complicated and uses the first algorithm as a subroutine. Throughout the paper, we assume
2.
Some Bounds
In this section we present some bounds regarding the multiple messages broadcasting problem.
The first two lemmas are simple extensions of the well-known lower bound for the 1-port case.
The first observation is that the broadcasting time of a single message among n processors in
the k-port model must take at least
log
\Upsilon
rounds. This is because after one round at most
processors know the message, after two rounds at most (k know the message, etc.
Lemma 1 The broadcasting time of one message among n processors in the k-port model is
at least
log
\Upsilon
rounds.
Our second observation is that the earliest round the broadcaster can send the m-th message
is after round dm=ke \Gamma 1 since in each round it can send at most k messages. Thus, the simple
lower bound follows.
Lemma 2 The broadcasting time of m messages among n processors in the k-port model is at
least
\Upsilon
log
\Upsilon
rounds.
However, for many combinations of n, m and k, we have a lower bound which is one
larger than the previous lower bound. The broadcast time of our second algorithm is also one
larger than the previous lower bound. Our second lower bound shows that in many cases this
algorithm is optimal. Specifically, we have the following lemma.
ne and let
then the lower bound for broadcasting m messages among n processors in the k-port model is
log
\Upsilon
Proof: Following the proof of Lemma 2, the broadcaster needs at least rounds to
send out all m messages. Furthermore, in the tightest schedule with respect to the broadcaster,
there are fi messages (where 1 - fi - need to be sent out at round t. For these fi messages
to reach all other processors, a total "bandwidth" of (n \Gamma 1)fi is needed starting from
round t. However, the maximum bandwidth that can be used for these fi messages starting
from round t are k; (k That is, at round t
log
\Upsilon
a total of n
bandwidth can be used for these fi messages. Thus, if (n at least one more
round is needed. 2
For example, when 2, the lower bound is dm=ke
log
\Upsilon
for
among all n in the range of
(i.e., the lower bound is dm=ke
log
\Upsilon
for among all n in the range
of As a special case when n is a power of k + 1, we have the following corollary.
Corollary 4 When n is a power of k + 1, the number of rounds required in broadcasting m
messages among n processors in a k-port model, k - 2, is at least
\Upsilon
log
\Upsilon
log k+1 n; otherwise.
Note that the \Gamma1 term appears only in the case where in the last round of sending by the
broadcaster, the broadcaster has only one message to send. Only in such cases the broadcaster
could start a complete broadcasting tree.
In this paper we circumvent this distinction between different values for m and k by considering
the minimum broadcasting time version of the problem. In this version we assume
that the broadcaster has an infinite number of messages and in each round it sends k new
messages to some k or less processors. These processors are responsible for broadcasting these
messages among the rest of the processors. The goal is to minimize the broadcasting time of
all messages. If we show that the maximum broadcasting time of any message is T rounds,
then the broadcasting time for m messages can be achieved in dm=ke simply
by instructing the broadcaster to be idle after it finishes sending all the m messages. Such a
reduction yields an algorithm which is optimal up to an additive term of
log
\Upsilon
from
the optimum. We summarize the above discussion in the following lemma.
Lemma 5 Suppose that there exists an algorithm for the minimum broadcasting time problem
the complexity of which is T rounds. Then there exists an algorithm for the multiple messages
broadcasting the complexity of which is far from the optimum by an additive term of at most
log
\Upsilon
rounds.
3 The k-Tree Algorithm
In this section, we describe a very simple algorithm, called the k-tree algorithm. The time
complexity of the algorithm is dm=ke+max(2; dlog k (n 2k)e). Thus, the delay of each message
is optimal up to a small multiplicative factor of log(k
3.1 A General k-Tree Theorem
Our algorithm is based on a construction of k spanning trees of size n each and a proper
labeling of the tree nodes. We first give a general theorem regarding k-port broadcast based
on k spanning trees.
Theorem 6 If one can construct k spanning trees (of size n each) with the properties that
1. for each tree, the n nodes are uniquely labeled from 0 through and the root is labeled
(the broadcaster),
2. the height of any tree is less than h, and
3. for each node (identified by a label) the number of children summing over all k trees is
at most k,
then broadcasting m messages among n nodes in the k-port model can be finished in time
Proof: For each round, the root (broadcaster) can send out a distinct message in each tree.
The messages are propagated down the tree with pipelining one level down per round. To make
sure such scheduling does not violate the k-port model, the number of incoming messages (and
outgoing messages, respectively) per round for each node must not exceed k. Clearly, each
non-root node will receive at most k messages per round, because it has one parent per tree.
Since, by Property 3, each node has at most k children summing over all k trees, the number
of outgoing messages per round is also bounded from above by k. The time complexity then
follows from Property 2. 2
3.2 Almost Complete k-ary Trees
The following definition is needed for our algorithm.
almost complete k-ary tree of n nodes, denoted T k (n), can be constructed
as follows. Starts from the root by adding nodes level by level in a top-down manner. Within
each level l, k leaf nodes are attached to each node of the level l \Gamma 1 from left to right until
either all nodes at this level have been filled or the tree has reached a total of n nodes.
We say that a node in a tree is an internal node if it is neither the root of the tree nor
a leaf node. Also, the root and the internal nodes are jointly referred to as non-leaf nodes.
Clearly, all the non-leaf nodes in T k (n) have k children except for the last non-leaf node which
has children. Also, only the last two levels can have leaf nodes. Since in
a complete k-ary tree of height h there are
nodes, it follows that
in such trees. Consequently, for other values of n the height of T k (n)
can be derived as
For convenience, we will also define T 0
k (n) a tree which is derived by attaching the root
of a T k (n \Gamma 1) to a new node, serving as the new root of T 0
k (n). We will broadcast based
on k spanning trees where each tree has the topology of T 0
possibly with some minor
modification. The goal is to find a mapping of f0; to each tree with node 0
mapped to the root, such that Property 3 of Theorem 6 is satisfied. We consider three cases
separately in the following: (i) k divides does not divide
2.
3.3 Broadcasting with k divides
We use k spanning trees for broadcasting, each of topology T 0
k (n). In a complete k-ary tree
with n nodes all the nodes can be counted in groups of k except of the root. Therefore, in a
complete k-ary tree k divides
k (n) is composed of T k (n \Gamma 1) trees, it follows that
when k divides every internal node in each of the T k (n \Gamma 1) tree has full fanout, i.e., k
children. Hence, in this case, the number of internal nodes per tree is (n \Gamma 2)=k and there are
a total of nodes over all k trees. Note that the broadcaster is the root of each
of the k trees. For all the other processors, we can choose of them and define a
one-to-one mapping to the nodes. Since each processor is mapped to an internal
node at most once (i.e., it is mapped to leaf nodes in all other trees), it has at most k children
summing over all k trees. Thus, by Theorem 6, the algorithm finishes in time dm=ke
where h is the height of these trees. Figure 1 shows an example of the
5 (12), used in broadcasting among processors with 5-port communication model.
3.4 Broadcasting with k does not divide
1. We first construct k trees, each having the topology
of T 0
These trees are labeled according to that described in the above case. We then
add ff nodes to each tree as follows.
For clarity, call these trees 0 through k \Gamma 1. We will add nodes to trees in the order from 0
to k \Gamma 1. For convenience, we refer to the first (resp. second) leaf node as the leaf node which
is of the first (resp. second) rank among all leaf nodes ordered in the top-down manner and
from left to right within each level. Note that since n - 2, the tree T 0
contains at
least and, therefore, has at least two leaf nodes. Let be the added
ff processors. In the process of adding these ff nodes we create new internal nodes. The
following algorithm has two tasks. First, it should specify to which parents these nodes are
attached. Second, it should assign a processor to the new internal nodes in a way that does
not violates Property 2 of Theorem 6. Note that there is no need to describe the assignment
of processors to leaves since any assignment is valid. The algorithm of attaching ff nodes to
each tree and assigning new internal nodes to the ff new processors is as follows.
attach ff nodes to the first leaf node of the j-th tree
and assign processor p i to the "new" internal node.
endif
else
attach nodes to the first leaf node of the j-th tree
and assign processor p i to the "new" internal node.
attach c nodes to the second leaf node of the j-th tree
and assign processor p i to the "new" internal node.
endif
endfor
Following the algorithm, the new ff nodes are either entirely attached to the first leaf node
or spread between the first and the second leaf nodes of T 0
ff). The counter c is used
to make sure that each processor p i will have at most k children summing over all k trees.
Since there are ffk new children need to be covered and each new processor can have up to k
children, there are enough processors to act as new internal nodes. Figure 2 shows an example
of the tree structure after adding nodes to that of Figure 1. Note that in this example
As in the previous example, processor 14 is not assigned to
any internal node.
3.5 Broadcasting with
For 2, the case is trivial. When 2, the above approach of adding
extra nodes to the case does not work, because there is only one leaf
node in T 0
(2). Thus, we need to redefine the "second" leaf in a dynamic way. Specifically,
we redefine the second leaf node as the first child of the first leaf node for this case. Then
the algorithm of attaching the ff nodes described above still holds. It is easy to show that the
maximum height of these trees is 3. Figure 3 shows an example of the trees for
5.
3.6 The Time Complexity
Let h be the maximum height of these trees. Then by Theorem 6, broadcasting m messages
can be realized in
\Upsilon
showed in Section 3.5 that h - 3.
We now derive h for the other cases.
Let f(n; which is the height of T k (n). The maximum height of
the k trees defined in Section 3.3 is k). The maximum height of the k trees defined
in Section 3.4 is 1 k. Here, the additive term of
2k in the first operand of the function f is an upper bound for the maximum number of nodes
that could be added while creating at most two new internal nodes. Now since f(n; k) is a
monotonely increasing function with respect to n, we only focus on the height of the second
case which is
Thus, the time complexity of our algorithm is at most
Note that 2 - k - thus the time complexity is also bounded from above by dm=ke
ne
Overall, for any n and any k - 2, the time complexity is bounded from above by
Recall that the simple lower bound is dm=ke
log
\Upsilon
1. Thus, the algorithm is about
a multiplicative factor of log(k above the lower bound in the delay-term, while the
bandwidth-term is tight. Table 1 lists, for some selected k and n, the number of additional
rounds required by this algorithm from the simple lower bound. For accuracy, we use the time
complexity of the k-tree algorithm before the approximation, i.e.,
when 2.
4 The Rotation Algorithm
In this section we describe a more complicated algorithm. This algorithm is based on three
broadcasting black-boxes described later. A broadcasting black box BBB(h; t; ffi) (referred also
as a system) is defined as follows:
ffl There are h processors in the system.
ffl In each round, k messages are injected into the system and are received by k or less
processors out of the h processors.
After ffi rounds these k messages are sent out of the system by k or less processors (not
necessarily the same processors).
ffl All the h processors know these k messages after at most t rounds.
The parameter t stands for the broadcasting time in this broadcasting black-box and the
parameter ffi stands for the delay time of the stream of messages from the time it is injected
into the system to the time it is ejected out of the system.
The trivial broadcasting black-box is the broadcaster itself. We denote this special black-box
by BBB(1; 0; 0) since we assume that the broadcaster already knows all the messages and
sends them with no delay.
Using broadcasting black-boxes, we can generate the broadcasting algorithm by chaining
black-boxes as follows. Let BBB broadcasting black-boxes where BBB 0
is the broadcaster black-box BBB(1; 0; 0) and BBB i is of the form BBB(h
we connect the output stream of messages of BBB i\Gamma1 to the input stream of
messages of BBB i . The output stream of BBB ' need not be sent. We refer to this algorithm
as the chain algorithm. The overall number of processors in the system is P '
. It is not
difficult to verify that the processors in BBB i know a message after P
rounds from
the time it was sent by the broadcaster. We get the following theorem:
Theorem 7 For broadcasting black-boxes
and let BBB be the trivial black-box consisting of the broadcaster. Then the
chain algorithm for BBB is a broadcasting algorithm among 1
processors which takes maxft
rounds.
Our algorithm is based on the following proposition regarding a representation of any
number n as a sum of ' properties.
Proposition 8 Any n - 1 can be represented as with the following
properties:
1. Either
2. Depending on the previous property, for any value of i between 1 and either ' or
log
\Upsilon
, and therefore ' !
log
\Upsilon
Proof: The proof is by construction. We first check whether
some d 1 - 1. If this is the case we are done. Otherwise, let (d 1 ; a 1 ) be the largest pair
(lexicographically) such that
the same process for finding \Delta. We are done either by finding
some
Clearly, d 1 -
log
\Upsilon
. In order to prove Property 3 we show that d 2 ! d 1 . The rest
follows the recursive construction. Assume to the contrary that d . we distinguish two
cases: (i) 1. In the first case, we get that
then the above inequality contradicts
the maximality of a 1 for a given choice of d 1 . If a 1
inequality contradicts the maximality of d 1 . In the second case the contradiction is achieved
since again
For the rest of the section we will describe the following three broadcasting black-boxes:
1. d) for some d -
2.
3. BBB(n; 2; 1) for n ! 2k.
We now use Proposition 8 to construct our chain algorithm. We apply the chain algorithm
on the black-boxes BBB(1; 0; 0), BBB(n case
We get the following corollary.
Corollary 9 In the above chain algorithm, the broadcasting time of any message is at most
log
\Upsilon
Proof: By Theorem 7 the complexity of the algorithm is maxfd
rounds. By the third property of Proposition 8, we get that d 1 - (j
and hence the round complexity is bounded by maxfd 2g. The corollary follows since
log
\Upsilon
log
\Upsilon
Note that in the above chain algorithm the delay of the stream of messages in the last
black-box is insignificant because the output stream is no longer needed. Therefore we can use
the types of black-boxes the delay of which is 1.
Now we return to our original multiple messages broadcasting algorithm. If all the messages
after the m-th message are null messages. Then the chain algorithm yields the following
theorem.
Theorem There exists a broadcasting algorithm among n processors which takes at most
\Upsilon
log
\Upsilon
rounds.
Note that this bound is greater than the simple lower bound by one. It matches the second
lower bound for many values of k, n, and m.
4.1 The Broadcasting Black Box for "nice" numbers
In this subsection we describe the broadcasting black-box BBB((k d) for some
d - 1. Let 1. This is a black-box for "nice" numbers, since together with the
broadcaster the system consists of processors, and since this algorithm is based on
some structure of the d-dimensional cube to the base of k + 1. Recall that in each round k new
messages enter the system and after a delay of d rounds, in each round, k different messages
leave the system. We denote these messages as input and output messages correspondingly.
Throughout the algorithm the processors are dynamically partitioned into disjoint sets. In
each round, each set of processors is instructed to send a message so that all the processors
in the set send the same message to k processors in other sets. It will be verified that any
processor receives at most k messages in this round. At the end of each round, processors are
instructed to move to a new set. However, the size of the sets remain the same.
First we define the partition of the processors. The partition consists of k \Delta d sets S i
1. The sets are arranged as a matrix of size k \Theta d. The size of set
these sets include all the
processors.
Denote the messages by M following the order they arrive to the black-box.
Next we define for each set what message to send. This definition depends on the round.
Assume that M enters the black-box at round 0 and let r - 1 be the current round.
All the processors in S i
are assigned the message M (r\Gamma1\Gammaj)k+i If (r
in the case of a finite number of message) then they are assigned no
message.
Now we define the recipients of the messages sent by each set of processors. For
the processors in S i
d\Gamma2 each sends k copies of its assigned message to processors in S i
.
In addition, the k input messages each goes to one of the sets S i
j. For the processors in
the set S i
send their assigned message to kjS i
processors and
one message as an output message. Indeed, this number is equal to
which is the number of all other processors.
We now verify that any processor receives at most k messages. The processors in S i
receive k messages from the sets S 1
. The processors
in S i
messages from the sets S 1
one message from a set S i
or an input message.
We conclude the description of the algorithm by defining the new partition of the processors.
The sets S 1
0 consist of the k processors that received the k input messages. The sets
consist of the processors in S i
all the processors
that received a message from them in this round. Note that processors change sets by going
in a circle manner among the sets S i
1. Some of the
processors remain in the set S i
throughout the algorithm.
Example: To demonstrate the flow of our algorithm we follow a message arriving at the
black-box until it is sent out of the black-box. Consider a processor x from the set S i
has just received the message M from the outside in round r. In round r
the only one who belongs to the set S i
0 . In this round x sends M to k processors from the
set S i
. These processors join x to create the new S i
1 set of round r + 2. In round r
these of M to k(k processors from the set S i
.
The recipients of the message M then join the senders to create the new S i
set of round r
the size of which is . This process continues in the same manner until round r d.
At the beginning of this round, x belongs to S i
and all the processors in this set knows M
and are assigned to send M to all other processors. We showed before that after this round all
the processor know M . Moreover, one of the processors, say x, can send M outside exactly d
rounds after x received M . At the same round x (or another processor from S i
gets a new
message from outside and the process starts again.
Correctness: The correctness of the algorithm is implied by the next lemma which states
the invariants maintained throughout the algorithm. Whenever we refer to a message M ' for
mean the null message.
Lemma 11 In the beginning of round r:
1. Message M (r\Gamma1\Gammaj)k+i is known to all processors in S i
2. Messages M are known to all processors.
Proof: The proof is by induction on the round number and follows the send, receive, and
movement instructions of the algorithm. 2
Following the dissemination of a particular message, it is not hard to see that the above
lemma implies the correctness of the BBB as stated in the next theorem.
Theorem 12 Any message is known to all processors after d rounds and leaves the system as
an output message after d rounds.
4.2 The Broadcasting Black Box for "special" numbers
In this subsection we describe the broadcasting black-box BBB(a(k
some d - 1 and 1 - a - k. Let a). This is a black-box for "special"
type of numbers which do not cover all numbers. Recall that in each round k new messages
enter the system and after a delay of one round these k messages leave the system. We denote
these messages as input and output messages. The algorithm is a variation of the algorithm
described in the previous subsection.
First we define the partition of the processors. The partition consists of k \Delta d sets S i
1. The sets are arranged as a matrix of size k \Theta d. For
the size of S i
and the size of S i
0 is one. Indeed,
these sets include all the
processors. The assignment of messages are the same as in the previous subsection.
Now we define the recipients of the messages sent by each set of processors. For
the processor in S i
sends k copies of its assigned message as follows: a \Gamma 1 copies to processors
from S i
a copies to processors to be specified later, and one copy is sent as an output
message. For each of the processors in S i
d\Gamma2 sends all of its k copies to
processors in S i
. In addition, the k input messages each goes to one of the sets S i
j. For the
processors in the sets S i
send their assigned message to k(k processors.
This number is kjS i
a). This means that there are k \Gamma a processors that
do not get the message assigned to the sets S i
. We choose these processors as processors
that always remain in their sets S i
and they receive this message d rounds earlier from the
processor of the set S i
The verification that each processor receives at most k messages and the new partition is
similar to the one appears in the previous subsection. Again, the correctness of the algorithm
follows the next lemma which states the invariants maintained throughout the algorithm.
Lemma 13 In the beginning of round r:
1. Message M (r\Gamma1\Gammaj)k+i is known to all processors in S i
2. Message M (r\Gamma2)k+i is known to k \Gamma a additional processors from a set S i 0
3. Messages M are known to all processors.
Proof: The proof is by induction on the round number and follows the send, receive, and
movement instructions of the algorithm. 2
Following the dissemination of a particular message, it is not hard to see that the above
lemma implies the correctness of the BBB as stated in the next theorem.
Theorem 14 Any message is known to all processors after d rounds and leaves the system as
an output message after one round.
4.3 The Broadcasting Black Box for "small" numbers
In this subsection, we describe the broadcasting black-box BBB(x; 2; 1) for 0 - x ! 2k.
Note that from the broadcasting black-box definition, the broadcaster is outside the box.
Thus, we consider broadcasting for 1 - n - 2k (n includes the broadcaster) using the k-tree
algorithm. For 1 2, we use the construction in Section 3.5 and the height
of the k trees is at most 3, which means the delay within the black box is at most 2. For
we use the construction in Section 3.4 and the height of the k trees is bounded
by 2.
Thus, the height h which means the delay within the black box is at
most 2. Note that we have in fact given a construction for BBB(x; 2; 2).

Summary

We have presented two algorithms for broadcasting multiple messages in the multiport model.
The k-tree algorithm has a very simple structure and scheduling policy. Furthermore, its time
complexity is very close to the lower bound for all practical k and n (see Table 1). The rotation
algorithm is optimal up to an additive term of one. For certain values of n we can use the
broadcaster to help broadcasting the messages to achieve an optimal algorithm. Since this
method does not work for all values of n we omit the description. Also, for some values of m
and k our algorithm is optimal. The exact characterization and finding optimal algorithms for
all values of n, are still open.
As mentioned in the introduction, in the Postal model even for there are not known
optimal algorithm for all values of n. Actually, for very few values of n there exist optimal
algorithms. The ultimate problem is to find an optimal algorithm for the k-port postal model
for the multiple messages broadcasting problem for any value of n, m, k, and - where - is the
delay parameter in the postal model (see [3]).



--R

The IBM external user interface for scalable parallel systems
CCL: a portable and tunable collective communication library for scalable parallel computers
Designing broadcasting algorithms in the postal model for message-passing systems
Multiple message broadcasting in the postal model
Optimal Multiple Message Broadcasting in Telephone-Like Communication Systems
PARIS: an approach to integrated high-speed private networks
Optimal multi-message broadcasting in complete graphs
Document for a standard message-passing interface
Express 3.0 Introductory Guide
Broadcast time in communication networks
Solving Problems on Concurrent Processors
The Intel Paragon XP/S supercomputer
A survey of gossiping and broadcasting in communication networks
Optimal broadcast and summation in the LogP model
The network architecture of the Connection Machine CM-5
The NCUBE family of parallel supercomputers
Architectures and Implementation of Vulcan
--TR
multiport model;message-passing system;one-to-all broadcast;broadcast;collective communication