Message Multicasting in Heterogeneous Networks.
In heterogeneous networks, sending messages may incur different delays on different links, and each node may have a different switching time between messages. The well-studied telephone model is obtained when all link delays and switching times are equal to one unit. We investigate the problem of finding the minimum time required to multicast a message from one source to a subset of the nodes of size k. The problem is NP-hard even in the basic telephone model. We present a polynomial-time algorithm that approximates the minimum multicast time within a factor of O(log k). Our algorithm improves on the best known approximation factor for the telephone model by a factor of $O(\frac{\log n}{\log\log k})$. No approximation algorithms were known for the general model considered in this paper.
Introduction
. The task of disseminating a message from a source node to
the rest of the nodes in a communication network is called broadcasting. The goal
is to complete the task as fast as possible assuming all nodes in the network participate
in the eort. When the message needs to be disseminated only to a subset
of the nodes this task is referred to as multicasting. Broadcasting and multicasting
are important and basic communication primitives in many multiprocessor systems.
Current networks usually provide point-to-point communication only between some
of the pairs of the nodes in the network. Yet, in many applications, a node in the
network may wish to send a message to a subset of the nodes, where some of them
are not connected to the sender directly. Due to the signicance of this operation, it
is important to design e-cient algorithms for it.
Broadcast and multicast operations are frequently used in many applications for
message-passing systems (see [11]). It is also provided as a communication primitive
by several collective communication libraries, such as Express by Parasoft [8] and
the Message Passing Library (MPL) [1, 2] of the IBM SP2 parallel systems. This
operation is also included as part of the collective communication routines in the
Message-Passing Interface (MPI) standard proposal [7]. Application domains that
use broadcast and multicast operations extensively include scientic computations,
network management protocols, database transactions, and multimedia applications.
Part of this work was done while the rst three authors visited IBM T.J. Watson Research
Center. A preliminary version of this paper appeared in the Proc. of the 30th ACM Symp. on
Theory of Computing, 1998.
y AT&T Research Labs, 180 Park Ave., P.O. Box 971, Florham Park, NJ 07932. On leave from
the Faculty of EE, Tel Aviv University, Tel Aviv 69978, Israel. E-mail: amotz@research.att.com.
z Computer Science Department, Stanford University, Stanford, CA 94305. Supported by
an IBM Fellowship, ARO MURI Grant DAAH04-96-1-0007 and NSF Award CCR-9357849, with
matching funds from IBM, Schlumberger Foundation, Shell Foundation, and Xerox Corporation.
E-mail: sudipto@cs.stanford.edu.
x Bell Laboratories, Lucent Technologies, 600 Mountain Ave., Murray Hill, NJ
07974. On leave from the Computer Science Department, Technion, Haifa 32000, Israel.
E-mail: naor@research.bell-labs.com.
{ IBM T.J. Watson Research Center, P.O. Box 218, Yorktown Heights, NY 10598.
E-mail: sbar@watson.ibm.com.
A. BAR-NOY, S. GUHA, J. NAOR AND B. SCHIEBER
In most of these applications the e-ciency depends on the time it takes to complete
the broadcast or multicast operations.
There are two basic models in which trivial optimal solutions exist. In the rst
model, all nodes are assumed to be connected, a node may send a message to at most
one other node in each round, and it takes one unit of time (round) for a message
to cross a link. Therefore, in each round the number of nodes receiving the message
can be doubled. If the target set of nodes is of size k, then this process terminates
in dlog ke rounds. In the second model the communication network is represented
by an arbitrary graph, where each node is capable of sending a message to all of
its neighbors in one unit of time. Here, the number of rounds required to deliver a
message to a subset of the nodes is the maximum distance from the source node to
any of the nodes in the subset.
The model in which a node may send a message to at most one other node in each
round is known as the Telephone model. It is known that for arbitrary communication
graphs, the problem of nding an optimal broadcast in the Telephone model is NP-hard
[12], even for 3-regular planar graphs [20]. Following the two easy cases given
above, it is not hard to verify that in the Telephone model two trivial lower bounds
hold for the minimum broadcast time. The rst one is dlog ne, where n denotes the
number of nodes in the graph, and the second one is the maximum distance from
the source node to any of the other nodes. Research in the past three decades has
focused on nding optimal broadcast algorithms for various classes of graphs such as
trees, grids, and hypercubes. Also, researchers have looked for graphs with minimum
number of links for which a broadcast time of dlog ne can be achieved from any source
node. Problems related to broadcast which were extensively investigated are the
problems of broadcast multiple messages, gossiping, and computing certain functions
on all n inputs in a network. See, e.g., [4, 5, 6, 9, 13, 14, 15, 19, 22, 24, 25].
An assumption central to the Telephone model is that both sender and receiver
are busy during the whole sending process. That is, only after the receiver received
the message, both ends may send the message to other nodes. More realistic models
in this context are the Postal model [3] and the LogP model [18]. The idea there is
that the sender may send another message before the current message is completely
received by the receiver, and the receiver is free during the early stages of the sending
process. We note that in both the Postal model and the LogP model it is assumed
that the delay of a message between any pair of nodes is the same.
Optimal solutions for broadcast in the Postal model are known for the case of a
complete graph, and for some other classes of graphs. However, not much is known
for arbitrary graphs. In the Postal model, researchers have also concentrated on other
dissemination primitives and almost always assumed that the communication graph
is complete.
1.1. Our results. In this paper we dene a more general model based on the
Postal model and call it the heterogeneous postal model. Assume node u sends a
message to node v at time 0 and the message arrives at v at time  uv . The assumption
is that u is free to send a new message at time s u , and v is free from time 0 to time
uv r v . We call  uv the delay of the link (u; v), s u the sending (or switching) time
of u, and r v the receiving time of v. By denition, both s u and r v are smaller than
uv . In the single message multicast problem each node receives no more than a single
message. Thus, for this problem the receiving time has almost no relevance. Because
of this, and to keep the presentation clearer we assume for the rest of the paper that
r nodes u. Observe that when the delay, sending time, and receiving
time are all equal to 1, we obtain the Telephone model.
We believe that our framework may be useful to model modern communication
networks, where the major components { the processors and the communication links
{ are not homogeneous. Some processors are faster than others, and some links have
more bandwidth than others. These disparities are captured by the dierent values
of the delay and the switching time.
Since nding the minimum multicast time is NP-hard even in the Telephone
model, we turn our focus to approximation algorithms. The main result we present is
an approximation algorithm for computing a multicast scheme in the heterogeneous
Postal model. The approximation factor is O (log k), where k denotes the number of
processors in the target set. Previous approximation algorithms for multicasting were
known only in the Telephone model. Kortsarz and Peleg [17] gave an approximation
algorithm that produces a solution whose value is bounded away from the optimal
solution by an O(
n) additive term. This term is quite large, especially for graphs
in which the broadcast (multicast) time is polylogarithmic. Later, Ravi [21], gave an
algorithm that achieves a multiplicative approximation factor of O
log n log k
log log k
We also show that it is NP-hard to approximate the minimum broadcast time
within a factor of three in a model which is only slightly more complicated than the
Telephone model.
The rest of the paper is organized as follows. In Section 2 we dene our model.
In Section 3 we describe our solution. Finally, in Section 4 we show that this problem
is hard to approximate by a small constant factor.
2. The Model and the Problem. We dene our model as follows. Let
(V; E) be an undirected graph representing a communication network, where V is a
set of n nodes and E is the set of point to point communication links. Let U  V
denote a special set of terminals, and let r be a special node termed the root. Let the
cardinality of the set U be k. To simplify notation assume that r 2 U .
We associate with each node v 2 V a parameter s v that denotes the sending
time. We sometimes refer to s v as the switching time of v to indicate that this is the
time it takes node v to send a new message. In other words, 1=s v is the number of
messages node v can send in one round (unit of time). We associate with each node
that denotes the receiving time. We assume that r
each node v. We associate with each link (u; v) 2 E a length  uv that denotes the
communication delay between nodes u and v. By denition,  uv is greater than both
s u and r v (= s v ). We can think of the delay  uv as taking into account the sending
time at u and the receiving time at v.
Let the generalized degree of node v 2 V be the actual degree of v in the graph
G multiplied by the switching time s v . Observe that the generalized degree measures
the time it would have taken the node v to send a message to all of its neighbors.
Our goal is to nd a minimum time multicast scheme; that is, a scheme in which
the time it takes for all nodes in the set U to receive the message from the root r is
minimized. Without loss of generality, we may consider only multicast schemes that
are \not lazy"; i.e., schemes in which a node that has not nished sending the message
to its neighbors (but has already started) is not idle. Such multicast schemes can be
represented by an outward directed tree T that is rooted at r and spans all the nodes
in U , together with orderings on the edges outgoing from each node in the tree. The
multicast scheme corresponding to such a tree and orderings is a multicast in which
each node in the tree upon receiving the message (through its single incoming edge)
sends the message along each of its outgoing edges in the specied order. From now
A. BAR-NOY, S. GUHA, J. NAOR AND B. SCHIEBER
on, we refer to the tree in the representation of a multicast scheme as the tree \used"
by the scheme.
For a rooted tree T , denote by  T its maximum generalized degree, and by L T
the maximum distance from r to any of the nodes in U (with respect to the lengths
xy associated with each link (x; y)). By denition, the multicast time of tree T is
greater than  T and greater than L T . Hence,
Lemma 2.1. Let OPT denote the multicast time of an optimal solution using
tree T  , then OPT  1( T
3. The Approximation Algorithm. In this section we describe the approximation
algorithm for multicasting a message to a set of terminals U from a root node
The main tool used by our algorithm is a procedure ComputeCore(U 0 ) that computes
for a given set of terminals U 0 , where r 2 U
1. A subset W  U 0 which we call the core of U 0 , of size at most 3jU 0 j, where
r 2 W .
2. A scheme to disseminate a message known to all the nodes in W to the rest
of the nodes in U 0 in time proportional to the minimum multicast time from
r to U 0 .
The algorithm that computes the multicast scheme proceeds in ' phases. Let U
Upon termination, U frg. In the ith phase,
is invoked to compute:
1. The core of U denoted by U i .
2. A scheme to disseminate the message from U i to the set U i 1 in time proportional
to the minimum multicast time from r to U i 1 .
we have that k). The resulting
multicast scheme is given by looking at the rounds of the algorithm in backward
order. Namely, starting at in each round of the multicast scheme
the message is disseminated from U i to U i 1 . Since U '  U ' 1      U each
dissemination phase takes time proportional to the minimum multicast time from r
to U . It follows that the multicast time is up to O(log times the optimal multicast
time.
In the rest of the section we describe the procedure ComputeCore(U 0 ). Let OPT
be the minimum multicast time from r to U 0 . Lemma 2.1 implies that there exists
a tree T  spanning the set U 0 such that  T  . The procedure
ComputeCore(U 0 ) has two main parts. In the rst part, we nd a set of jU 0 j paths,
one for each terminal, where the ith path connects the terminal u i to another terminal
called The paths have the following path properties:
Length Property: The length of each path is at most 4  ( T
Congestion Property: The generalized degree of the nodes in the graph induced
by the paths is at most 6  ( T
In the second part we design a dissemination scheme using the above paths. We do
it by transforming the paths into a set of disjoint spider graphs { graphs in which
at most one node has degree more than two. These spider graphs have the following
spider properties:
Each spider contains at least two terminals from U 0 .
The set of spiders spans at least half the nodes in U 0 .
The diameter of each spider is at most 4  ( T
The generalized degree of the center of a spider is at most 6  ( T
where the center of a spider is the unique node with degree larger than two,
if such exists, or one of the endpoints of the spider, otherwise.
Now, for each spider, we arbitrarily select one of the nodes from U 0 to the core of U 0 .
Note that each such node can multicast the message to the rest of the terminals in its
spider in O( T  +L T ) time (linear in OPT ). We add all the terminals not contained
in any of the spiders to the core of U 0 . We claim that the size of the core is at most4
To see this, let x denote the number of spiders and let y be the number of the
terminals in all the spiders. It follows that the size of the core is jU x. By the
rst spider property we have that x  y=2 and by the second spider property we get
that y  jU 0 j=2. Thus,
We now turn to describe each of the two parts of the procedure ComputeCore(U 0 ).
3.1. Finding a set of paths. We rst claim the following lemma which is
analogous to the \tree pairing" lemma of Ravi [21].
Lemma 3.1. Let T be a tree that spans a set U 0  V , and suppose that jU 0 j
is even. There exists a way to pair the nodes of U 0 , and nd paths (in the tree T )
connecting each pair such that:
1. the paths are edge disjoint,
2. the length of each path is bounded by 2L T ,
3. the generalized degree of each node in the graph induced by the paths is at
most  T .
Proof. The tree pairing lemma ([21]) states that there exists a pairing such that
the paths in T connecting each of the pairs are edge disjoint. Consider these paths.
Clearly the length of each of these paths is bounded by 2L T . The degree, and hence
the generalized degree, of every node in the graph induced by the paths is no more
than the (generalized) degree in T since we only use the edges of the tree T . Hence,
it is bounded by  T .
The following corollary handles the odd case as well.
Corollary 3.2. Let T be a tree that spans a set U 0  V . There exists a way to
pair the nodes of U 0 , and nd paths (in the tree T ) connecting each pair such that:
1. the length of each path is bounded by 2L T ,
2. the generalized degree of each node in the graph induced by the paths is at
most 2 T .
Proof. The corollary clearly holds if jU 0 j is even. If jU 0 j is odd, we pair jU 0 j 1 of
the nodes as in Lemma 3.1, and pair the last node with any other node. The length
of the path connecting the last pair is still bounded by 2L T . However, the degree of
the subgraph may double up to 2 T .
Recall that the tree T  spans the nodes of U 0 and Our
objective is to nd the set of paths as guaranteed by Corollary 3.2 with respect to
T  . However, we do not know T  . Thus, instead, we nd a set of fractional paths
satisfying similar properties. To this end, we write a linear program for nding a set
of (fractional) paths that minimizes the sum of two quantities: (1) the maximum over
all pairs of the average length of the paths connecting a pair, and (2) the maximum
generalized degree of the subgraph induced by the paths connecting the pairs.
The linear program is a variant of multicommodity
ow. For each edge (u; v), we
dene the directed edges (u; v) and (v; u) both of length  uv . Let U g.
With each node v j 2 U 0 we associate commodity j. Node v j is the source of commodity
j and we create an articial sink t j with r t j
We connect each of the nodes
A. BAR-NOY, S. GUHA, J. NAOR AND B. SCHIEBER
by a directed edge (v The objective is
to minimize (L exactly one unit of
ow has to be shipped from each v j
to t j , such that the average length of the
ow paths from v j to t j is at most 2L, and
the maximum weighted congestion (generalized degree) of the induced subgraph is at
most 3.
More formally, let A denote the set of directed edges, and let f i (u; v) denote the
ow of commodity i on directed edge (u; v). The linear programming formulation is
as follows.
subject to:
For all 1  i  h
and
(v;w)2A
For all 1  i
For all 1  i
(v i ;u)2A
For all 1  i
For all
3
For all 1  i
We now show that the set of paths guaranteed by Corollary 3.2 with respect to T
can be modied so as to obtain an integral solution for the linear program as follows.
If jU 0 j is even, the solution is obtained by using each path connecting a pair
to ship one unit of
ow from u j through u i to t j , and another unit of
ow from u i
through u j to t i . The length of each path is bounded by 2L T  , and since we use each
path twice, the generalized degree is bounded by 2 T  . If jU 0 j is odd, the solution is
obtained by using each of the 1(jU 0 j 1) paths connecting the rst jU nodes of
twice (once in each direction), and using the path connecting the last node in U 0
to its mate to ship
ow out of this node. The length of each path is still bounded by
However, because of the additional path, the degree is only bounded by 3 T  .
It follows that the value of the objective function for this solution is  T  +L T  ,
and thus the linear program is guaranteed to nd a solution whose value is upper
bounded by this value. Let L T and  T denote the values of the length and congestion
in the optimal solution of the above linear program.
The optimal solution is a \fractional" solution in the sense that the (unit)
ow of
each commodity is split between several
ow paths. We round the fractional solution
into an integral solution using an algorithm proposed by Srinivasan and Teo [23].
This algorithm builds on a theorem proved by Karp et al. [16]. For completeness and
since the details are slightly dierent, we now describe the rounding of the fractional
solution.
Theorem 3.3. [16] Let A be a real valued r  s matrix, and y be a real valued
s-vector. Let b be a real valued vector such that Ay = b. Let t be a positive real number
such that in every column of A,
1. the sum of all positive entries  t, and
2. the sum of all negative entries  t.
Then, we can compute (in polynomial time) an integral vector
y such that for every
t.
We now show how to nd an integral
ow of congestion at most 6 T +4L T , where
each
ow path (of each commodity) has length at most 4L T . We rst decompose the
ow into (polynomially many)
ow paths. If any path in this decomposition is longer
than 4L T , we discard it. We observe that since the average length is less than 2L T ,
discarding these long paths leaves at least half of a unit of
ow between each pair
(v We scale the
ows appropriately such that the total
ow to each t i is exactly
1. This can at most double the
ow on an edge, and the total congestion is now at
most 6 T .
denote the length bounded
ow paths. Denote the set of nodes in
a path P i by V (P i ) and the set of edges by E(P i ). Let f(P i ) denote the amount of
ow pushed on path P i . Dene the set P j as the set of all paths that carry
ow of
the jth commodity. Observe that each path belongs to exactly one P j . The linear
system needed for Theorem 3.3 is dened by the following linear equations,
where the i-th equation corresponds to the i-th row of A and the i-th element of b.
for each v s v
i:
for all j 4L T
The second set of inequalities captures the fact that the
ow on all the paths
corresponding to commodity j is exactly 1. Now the sum of the positive entries in a
column is
(length of path
The second part of the inequality follows since s v   vw for all v; w and s t j
sum of the negative entries in a column is at most 4L T , this follows due to the fact
that each P i belongs to exactly one P j . Invoking Theorem 3.3 gives us a set of paths
such that,
for each v s v
i:
for all j 4L T
The second set of inequalities implies that each commodity has at least one
ow
path. So we have a set of
ow paths such that the congestion is at most 6 T
and their length is at most 4L T . Since  T +L T   T  +L T  these paths satisfy the
length and congestion properties as desired.
3.2. Finding a spider decomposition. We now show how to obtain a spider
decomposition satisfying the spider properties previously dened. Recall that we are
now given a set of paths connecting each terminal u j with another terminal Mate(u j ),
and that this set of paths satises the length and congestion properties.
We nd a set of at least jU 0 j=2 trees that satisfy the following properties which
are similar to the spider properties.
A. BAR-NOY, S. GUHA, J. NAOR AND B. SCHIEBER
Each tree spans at least two terminals from U 0 .
The diameter of each tree is at most 4L T  4  ( T
The generalized degree of each node in each of the trees is at most 6 T
Before showing how to nd these trees, we show how to transform them into the
required spiders. Repeatedly, consider the tree edges, and remove a tree edge if
it separates the tree into two subtrees such that either, both subtrees contain at
least two terminals, or one of them contains no terminals (in this case this subtree
is removed as well). Repeat this process until no more edges can be removed. The
process terminates since the number of edges is nite. Observe that upon termination,
if a connected component is not a spider, then another edge could be deleted. Thus,
we get the following claim.
3.4. When the process terminates each connected component is a spider.
Clearly, all the terminals spanned by the trees are also spanned by the spiders.
The diameter of each of these spiders is at most 4L T , since the distance between
every pair of nodes in U 0 spanned by a tree is at most 4L T to begin with. Also, the
generalized degree of the \center" of the spider is at most the generalized degree of
its originating tree since we have not introduced any new edges in the process. We
conclude that the spiders satisfy the desired spider properties.
Now, we show how to nd the required trees. Dene G p to be the undirected
graph induced by the paths from each terminal to its mate. Observe that a spanning
forest of this graph may not satisfy the required diameter property above and hence
some extra renement is necessary.
For each node u in G p , nd a unique terminal in U 0 that is closest to u (with
respect to the lengths  xy associated with each link (x; y)). Ties are broken arbitrarily.
We modify the paths starting at each terminal as follows. From each terminal u
begin tracing the path connecting u to Mate(u). At some node v along this path,
the closest terminal to v will not be u. We are guaranteed to encounter such a node
because the closest node to Mate(u) is Mate(u) itself. From this node v trace the
path to its closest terminal. This creates a path from u to another terminal denoted
NewMate(u). Note that NewMate(u) may be dierent from Mate(u). However, we
are guaranteed that the path from u to NewMate(u) is not longer than the path from
u to Mate(u) and thus bounded by 4L T .
Dene an auxiliary directed graph H on the set of terminals U 0 with the set of
edges . By denition each node in H has outdegree
one. Thus, each connected component of (the undirected skeleton of) H contains
exactly one directed cycle. Discard one edge from each such connected component to
make it a rooted tree in which all edges are oriented towards the root. (The root is
unique since the outdegree of each node is one.) Note that every non-trivial strongly
connected component of H is a cycle. Thus, this can be done just by discarding an
arbitrary edge from each strongly connected component of H . Let H 0 be the resulting
forest.
Dene the level of a node in H 0 to be the number of edges in the path to it from
the root of its component. (We
ip the direction of the edges in H 0 for the purpose
of measuring distances.) Distinguish between nodes of even level and nodes of odd
level. Each edge of H 0 goes either from an odd level node to an even level node or
vice-versa.
Consider two collections of stars in H 0 . One collection consisting of edges from
odd level nodes to even level nodes, and the other consisting of edges from even level
nodes to odd level nodes. Every terminal with positive indegree and outdegree (in
spanned by a star in each one of the two collections. Every terminal with
either indegree or outdegree zero (in H 0 ) is spanned by a star in only one of the two
collections. However, by a simple pigeon-hole argument, at least one of the collections
spans at least half of the terminals.
Consider such a collection. First, note that each star in this collection induces an
undirected tree in the original graph when replacing each star edge by its originating
path. We now claim the following,
Lemma 3.5. The induced trees of any two stars belonging to the same collection
are node disjoint.
Proof. To obtain a contradiction assume they are not disjoint. Then, there exist
two distinct terminals with the same even or odd parity, say u and v, such that
NewMate(u) 6= NewMate(v), but the paths traced from u to NewMate(u) and
from v to NewMate(v) have a common node x. Consider the terminal chosen by x
as its closest terminal. We distinguish between two cases.
Case 1: The terminal chosen by x is u. Then u must be NewMate(v), contradicting
the fact that u and v are of the same parity. The case where v is the chosen terminal
of x is symmetric.
Case 2: The terminal chosen by x is NewMate(u). Then NewMate(v) must be the
same as NewMate(u); a contradiction. The case where NewMate(v) is the chosen
terminal of x is symmetric.
It is easy to see that the trees induced by the stars in the collection satisfy the
required properties. This concludes the construction.
4. Hardness of Approximations. In this section we show that the best possible
approximation factor of the minimum broadcast time in the heterogeneous Postal
model is 3 . We show this hardness result even for a restricted model in which
d. Note that when s
broadcast the message concurrently to all of its neighbors. The proof is by a reduction
to the set cover problem. In the unweighted version of the set cover problem we are
given a set U of elements and a collection S of subsets of U . The goal is to nd the
smallest number of subsets from S whose union is the set U . Feige [10] proved the
following hardness result.
Lemma 4.1. Unless NP  DT IME(n log log n ), the set cover problem cannot be
approximated by a factor which is better than ln n, and hence it cannot be approximated
within any constant factor. In our proof, we will only use the fact that it is NP-Hard
to approximate the optimal set cover within any constant factor.
Theorem 4.2. It is NP-Hard to approximate the minimum broadcast time of any
graph within a factor of 3 .
Proof. Assume to the contrary that there exists an algorithm that violates the
claim of the theorem for some . We show how to approximate the set cover problem
within a constant factor using this algorithm.
To approximate the set cover problem we "guess" the size of the optimal set cover
and use our approximate minimum broadcast time algorithm to check our guess. Since
the size of the optimal set cover is polynomial, we need to check only a polynomial
number of guesses.
Consider an instance of set cover I = (U; S) where U is the set of elements, and
S a collection of subsets of U . Let jU m. Let the guess on the size
of the optimal set cover be k. We construct the following graph G. The graph G,
consists of 1 vertices: a distinguished root vertex r, vertices e
A. BAR-NOY, S. GUHA, J. NAOR AND B. SCHIEBER
corresponding to the elements of U , vertices um corresponding to the subsets,
and k additional vertices a
r
e
ae1
a
The root r has switching time and is connected to a by edges
with delay  ra '
= 1. Each vertex a ' has switching time s(a ' connected
to all u j with delay  a ' u j
= 1. Each vertex u j has switching time
connected to a vertex e i i the jth set contains the ith element. The delay of such
an edge is  u
d, where d > 4 2
is a constant. Each vertex e i has switching time
1. Finally, to complete the instance of the multicasting problem, the target
multicast set consists of all vertices e i .
We rst show that if there is a set cover of size k, then there is a multicast scheme
of length d 2. After time 1, all the vertices a ' receive the message. After time 2,
all the vertices u j corresponding to sets which are in this cover, receive the message.
This is possible since all a ' are connected to all u j . Finally, these vertices send the
message to all the elements that they cover. Since s(u j
that the multicast time is d 2.
Suppose that the algorithm for the multicasting problem completes the multicasting
at time t. By the contradiction assumption, its approximation factor is 3 .
Since by our guess on the size of the set cover the optimal multicast time no more
than d+2 we have t  (3 )(d 2.
The strict inequality follows from the choice of d.
We rst claim that all the vertices u j that participate in the multicast receive the
message from some a ' . Otherwise there exists a vertex e i 0 that received the message
via a path of a type (r; a This means that e i 0 received the message at
or after time 3d t. Our second claim is that each vertex a ' sends the message
to at most 2d vertices u j . This is because the (2d 1)st vertex would receive the
message at time 2d would not be able to help in the multicast eort that is
completed before time 3d 2.
Combining our two claims we get that the multicasting was completed with the
help of 2dk vertices u j . The corresponding 2dk sets cover all the elements e i . This
violates Lemma 4.1 that states that the set cover problem cannot be approximated
within any constant factor.
Remark:. In our proof we considered a restricted model in which the switching
time may only get two possible values and the delay may get only three possible values
(assuming that when an edge does not exist then the delay is innity). Observe that
this hardness result does not apply to the Telephone model in which the switching
time is always 1 and the delay is either 1 or innity. We have similar hardness results
for other special cases. However, none of them is better than 3 and all use similar
techniques.

Acknowledgment

. We thank David Williamson for his helpful comments.



--R

The IBM external user interface for scalable parallel systems
CCL: a portable and tunable collective communication library for scalable parallel comput- ers
Designing broadcasting algorithms in the Postal model for message-passing systems
Optimal Multiple Message Broadcasting in Telephone-Like Communication Systems
Optimal multi-message broadcasting in complete graphs
Algebraic construction of e-cient networks
Document for a standard message-passing interface
Express 3.0 Introductory Guide
Broadcast time in communication networks
A threshold of ln n for approximating set cover
Solving Problems on Concurrent Processors
Computers and Intractability: A Guide to the Theory of NP-Completeness
On the construction of minimal broadcast networks
Tight bounds on minimum broadcast networks
A survey of gossiping and broadcasting in communication networks
Global wire routing in two-dimensional arrays
Approximation algorithm for minimum time broadcast
Optimal broadcast and summation in the LogP model
Broadcast networks of bounded degree
Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2
Rapid rumor rami
Generalizations of broadcasting and gossiping
A constant-factor approximation algorithm for packet routing
A new method for constructing minimal broadcast networks
A class of solutions to the gossip problem
--TR

--CTR
Teofilo F. Gonzalez, An Efficient Algorithm for Gossiping in the Multicasting Communication Environment, IEEE Transactions on Parallel and Distributed Systems, v.14 n.7, p.701-708, July
Michael Elkin , Guy Kortsarz, Sublogarithmic approximation for telephone multicast, Journal of Computer and System Sciences, v.72 n.4, p.648-659, June 2006
David Kempe , Jon Kleinberg , Amit Kumar, Connectivity and inference problems for temporal networks, Journal of Computer and System Sciences, v.64 n.4, p.820-842, June 2002
Pierre Fraigniaud , Bernard Mans , Arnold L. Rosenberg, Efficient trigger-broadcasting in heterogeneous clusters, Journal of Parallel and Distributed Computing, v.65 n.5, p.628-642, May 2005
Eli Brosh , Asaf Levin , Yuval Shavitt, Approximation and heuristic algorithms for minimum-delay application-layer multicast trees, IEEE/ACM Transactions on Networking (TON), v.15 n.2, p.473-484, April 2007
postal model;logp model;combinatorial optimization;approximation algorithms;heterogeneous networks;multicast