Time and Cost Trade-Offs in Gossiping.
Each of n processors has a value which should be transmitted to all other processors. This fundamental communication task is called gossiping. In a unit of time every processor can communicate with at most one other processor and during such a transmission each member of a communicating pair learns all values currently known to the other.Two important criteria of efficiency of a gossiping algorithm are its running time and the total number of transmissions. Another measure of quality of a gossiping algorithm is the total number of links used for transmissions. This is the minimum cost of a network which can support the gossiping algorithm. We establish trade-offs between the time T of gossiping and the number C of transmissions and between the time of gossiping and the number L of links used by the algorithm. For a given T we construct gossiping algorithms working in time T, with parameters C and L close to optimal.
Introduction
Gossiping (also called all-to-all broadcasting) is one of the fundamental tasks in network
communication. Every node of a network (processor) has a piece of information (value)
which has to be transmitted to all other nodes, by exchanging messages along the links
of the network. Gossiping algorithms have been extensively studied, especially in the last
twenty years; see the comprehensive surveys [5, 8] of the domain.
The classical communication model, already used in the early papers on gossiping [1, 2, 3,
7, 14], is called the 1-port full-duplex model. Communication is synchronous. In a single
round (lasting one unit of time) every node can communicate with at most one neighbor and
during such a transmission communicating nodes exchange all values they currently know.
Two important criteria of efficiency of a gossiping algorithm are its running time (the number
of communication rounds) and the total number of transmissions (calls). The latter is a
measure of cost of the algorithm, assuming unit charge per call. The minimum time of
gossiping in a complete n-node network was the first problem in this domain, studied in the
fifties [2, 14]. It was proved to be dlog ne for even n and dlog ne On the other
hand, the minimum number of calls in gossiping is 2n \Gamma 4, for any n ? 3 (cf. [1, 7]).
Another measure of quality of a gossiping algorithm is the total number of links used for
communication. This is the minimum cost of a network which can support the algorithm,
measured by the number of links in the network. This can be also viewed as a measure of
the cost of implementing the algorithm, a fixed cost associated with network design, rather
than the cost associated with each run. Clearly, the sparsest network supporting gossiping
is a tree and thus the minimum number of links is n \Gamma 1.
It turns out that the above criteria of efficiency are incompatible: it is impossible to minimize
time and the number of calls or to minimize time and the number of links used by the
algorithm, simultaneously. If every gossiping algorithm working in time r must have
both the number of calls and the number of links used for communication equal to r2
as every node has to communicate in every round with a different node, in order to double
its knowledge. On the other hand, Labahn [11] proved that the minimum running time of
a gossiping algorithm with the number of calls 2n \Gamma 4 is 2dlog ne \Gamma 3, almost a double of
the absolute minimum time. (An earlier proof of this fact, published in [15], was incorrect.)
Likewise, in order to minimize the number of links used for communication, we must allow
larger gossiping time. Labahn [10] proved that the minimum gossiping time in a tree is at
least 2dlog ne \Gamma 1, again almost a double of the absolute minimum time.
These results indicate the existence of time vs. cost trade-offs in gossiping, where cost is
measured either by the number C of calls or by the number L of links used for communication.
Establishing these trade-offs is the main goal of the present paper. For a given T (ranging
from log n to 2log n) we show upper and lower bounds on the minimum cost of gossiping in
time T . The algorithms yielding our upper bounds are generalizations of known gossiping
schemes that minimized separately either the running time or the cost (cf. [1, 2, 3, 7, 11,
14, 15]). While these classical algorithms were either fast but costly or cheap but slow, it
turns out that they can be combined to yield almost optimal cost for any given running
time. However, the main contribution of this paper are lower bounds on the minimum cost
of gossiping for a given running time, that closely match the performance of our respective
algorithms. This is for the first time that the full spectrum of relations between the time
and the cost of gossiping is investigated.
Each of our bounds is useful for a different range of values of the running time and cost.
If the running time is ne + t(n), we show an upper bound 2n + O( nlog n
) on the
number of calls, which closely matches the lower
) following from [12] . These
bounds are useful for small t(n), i.e., when the running time is small. If the running time
is ne \Gamma r(n), we show an upper bound 2n + O(r(n)2 r(n) ) and a lower bound
log
These bounds are useful for small r(n), i.e., when the running time is larger.
Here are a few consequences of the above results. Let the running time T of gossiping be
equal to dlog ne+ t(n). Let C denote the minimum number of calls in time T . The following
sequence of bounds shows how C gradually decreases from \Theta(nlog n) to the asymptotically
optimal range 2n + o(n), as restrictions on T are being relaxed.
If t(n) is constant then C 2 \Theta(nlog n).
If
If t(n) - log log n \Gamma d, for a constant d, then C 2 O(n).
If
For medium range values of the running time T we obtain the following bounds on the
minimum number of calls:
If
log
Finally, if we want to keep the number of calls very small, time has to increase significantly:
If
We also establish trade-offs between the time T of gossiping and the minimum number L of
links used for communication. For medium and large values of T the optimum values of L are
roughly one-half of the values of C for the same time. In this range we get bounds that are
even tighter than in the case of the number C of calls. For example, if
log n) and L
log n ). For small values
of we obtain the upper bound n + O( nlog n
on L but our lower bound
leaves a larger gap than before: we show that if t(n) - c log log log n, for
It remains open, for example, if L 2 \Omega\Gamma nlog n) for
constant t(n).
The latter bound should be contrasted with a result of Grigni and Peleg [6], concerning
broadcasting. They showed that the minimum number of links in an n-node network supporting
broadcasting from any node in a given time T is extremely sensitive to the value of
is a power of 2, broadcasting in time log n
links, while broadcasting
in time log can be performed in a network with O(n) links. Our bound shows that
this is not the case for gossiping: in particular, gossiping in time log const cannot be
performed in a network with a linear number of links.
It turns out that the problem of minimizing the cost of gossiping with a given running time
has a different flavor in the case of the number of calls and of the number of links. While
the same algorithms provide upper bounds in both cases, the techniques used to prove lower
bounds are different and results concerning one of these performance measures do not seem
to imply meaningful bounds for the other, in any straightforward way.
The paper is organized as follows. In section 2 we introduce the terminology and state some
preliminary results used in the sequel. Section 3 is devoted to the description of a class of
gossiping algorithms and computing their running time, number of calls and number of links
used for communication. These results yield upper bounds on the minimum cost of gossiping
with a given running time. In section 4 we establish lower bounds on the number of calls
in gossiping with a given running time. In section 5 we give lower bounds on the number
of links used in gossiping with a given running time. In section 6 we derive consequences
of previous results by applying them with appropriate parameter values. Finally, section 6
contains conclusions and open problems.
preliminaries
The set of communicating nodes is denoted by X and its size is denoted by n. A calling
scheme S on the set X is a multigraph on X whose edges are labeled with natural numbers
t, so that edges sharing a common node have different labels. Edges with label i
represent calls made in the ith time unit. The number of labels is called the running time
of the scheme and the number of edges is called the number of calls of the scheme. The
corresponding multigraph is called the graph of calls of the scheme S. The underlying graph
of a calling scheme S is the simple graph on the set X of nodes in which adjacent nodes
are those joined by at least one edge in S. This is the minimal network that supports the
scheme S. The number of edges in the underlying graph of S is called the number of links
used by S.
Upon completion of S the node v knows the value of the node w if there exists an ascending
path from w to v in S, i.e., a path with increasing labels on edges. The set of nodes who know
the value of v upon completion of S is denoted by K(v) and the set of nodes whose value v
knows upon completion of S is denoted by K \Gamma (v). If the
calling scheme S is called a gossiping scheme or gossiping algorithm. The (total) knowledge
upon completion of the calling scheme S is the number
(v)j. The knowledge
after i rounds is at most for every node v. The knowledge at the
end of a gossiping scheme is n 2 .
Lemma 2.1 1. If the calling scheme has k calls then jK(v)j
for every node v.
2. If the running time of a calling scheme is t then jK(v)j
node v.
Lemma 2.2 If then the time required for the remaining nodes to learn the
value of v is at least log n \Gamma log k.
Proof: One of the k informed nodes has to inform at least n\Gammak
other nodes which requires
time at least log n
All logarithms are with base 2. The notation
O,\Omega and \Theta is standard. We use o(f(n)) (resp.
!(f(n))) to denote the class of functions g(n), such that g(n)
converges to 0, as
grows.
3 Gossiping algorithms and upper bounds
In this section we present a class of gossiping algorithms that provide good time and cost
trade-offs, both in the case when cost is measured by the number of calls and when it is
measured by the number of links used for communication. Two important graphs will be
used in the construction of our schemes. The first is the k-dimensional hypercube H k . This
is the graph on 2 k nodes labeled with all binary sequences of length k. Nodes are adjacent
iff their labels differ in exactly one position. Nodes whose labels differ in the jth position
are called j-neighbors.
The second graph is the k-broadcasting tree B k . It is defined by induction on k. B 0 is a
single node v. B k+1 is obtained from B k by attaching a different new node to every node of
. The set of all new edges is called the 1)th layer in B k+1 . The initial node v is called
the root of the broadcasting tree.
Hypercubes and broadcasting trees are important for gossiping. Giving label j to edges of
the hypercube H k joining j-neighbors yields a gossiping scheme with the smallest running
time k. The cost of this scheme, however, is very large: it uses k2 k\Gamma1 calls and k2 links.
On the other hand, broadcasting trees yield gossiping schemes with small cost but large time.
Replace every edge in layers by two edges: one with label
the other with label k 1). Give label k to the edge in layer 1. The obtained gossiping
scheme first gathers all values in the root and then broadcasts them all to all nodes. Its
running time is its cost is very low: if is the number of nodes, it has the
optimal number links and it uses 2n \Gamma 3 calls, only one call more than the absolute
minimum.
In order to save gossiping time at a given cost or to lower cost with a given running time,
it is advantageous to use a combination of the two above schemes. Let
ne \Gamma 1. Let r - k and We describe the gossiping
algorithm COT(n; r). (COT stands for Cube of Trees.) Consider the hypercube H r and let
each of its nodes be the root of a broadcasting tree B s . Trees rooted at distinct nodes of
H r are disjoint. There are 2 k nodes in all trees. Attach each of the remaining x nodes to a
distinct node in one of the trees. Define the set of edges incident to these nodes to be the
Replace each edge of layers by two edges with labels s
Finally give label s to edges of the hypercube H r
joining i-neighbors.
The above described gossiping scheme works as follows: first information from all nodes of
the tree rooted at a given node of the hypercube is gathered in this node. Then gossiping
is executed inside the hypercube H r among all its nodes. At this point all nodes of the
hypercube know all values. Finally each node of the hypercube broadcasts the complete
information to all nodes of the tree rooted at it. The underlying graph of the scheme
COT(n; r) is the undirected version of the graph H r;s used in [6] for broadcasting.
Theorem 3.1 The gossiping algorithm COT(n; r) has running time uses
links.
Proof: Gathering information in nodes of H r takes time gossiping in H r takes time
r and broadcasting complete information in trees takes time total of
Gathering information in nodes of H r uses 2 r gossiping in H r uses r2
calls and broadcasting complete information in trees uses again 2 r calls, for a
total of
The number of links in the hypercube H r is r2 r\Gamma1 , the total number of links in all trees is
a total of
The above theorem yields upper bounds on the cost of gossiping with a given running time.
It will be convenient for our purposes to formulate them in two versions:
Corollary 3.1 For any functions t; r : N ! N , such that t(n); r(n) - dlog ne, there exists
a gossiping algorithm
1. with running time ne \Gamma r(n), number of calls C 2 2n +O(r(n)2 r(n) ) and using
2. with running time ne number of calls C
using
links.
Proof: 1. Straightforward.
2. Use part 1. for
The above corollary shows that there exists a gossiping algorithm whose time and cost are
both asymptotically optimal, i.e., whose running time is log n) and which uses
links. To this end it suffices to take, e.g.,
However, the results of the following sections will enable us to establish time and cost trade-offs
more precisely.
Lower bounds on the number of calls
In this section we give two lower bounds on the number of calls in gossiping with a given
running time. Each of them provides meaningful consequences for a different range of time
and cost values. The first bound follows directly from a result of Labahn [12] and is useful
for small values of the running time.
Theorem 4.1 Every gossiping algorithm with running time
calls.
The next theorem yields lower bounds on the number of calls in gossiping that are useful
when the running time is larger. We first prove two lemmas.
Lemma 4.1 If a calling scheme has the running time at most t and its graph of calls is a
tree then:
1. there exists a node v such that jK(v)j - t
2. there exists a node v such that
Proof: We prove only the first part of the lemma: the second part is analogous. Call a node
terminal if there is no ascending path of length larger than 1, starting from v. It suffices
to prove that there exists a terminal node v. Indeed, for such a node, K(v) consists of v
itself and of its neighbors in the tree of calls. The desired inequality follows from the fact
that the number of neighbors of a node in the graph of calls cannot exceed the running time
of the calling scheme.
Choose any node w 0 and suppose that it is not terminal. Choose any ascending path
(w 2. If w 2 is terminal, we are done, if not, choose any ascending path
(w length 2, and so on. Since labels in each path are strictly increasing and the
graph of calls is a tree, at every step at least one new node is visited. Thus the process must
terminate at some node w k which has to be terminal. 2
Lemma 4.2 If a calling scheme on n nodes has the running time at most t and uses at most
1. there exists a node v such that jK(v)j - t
2. there exists a node v such that
Proof: Again we prove only the first part of the lemma. Suppose that S is a calling scheme
satisfying the assumptions but violating assertion 1. Let a 1 ; :::; a k be the numbers of nodes in
components of the graph of calls of S. No component has a node v such that jK(v)j - t + 1.
It follows from lemma 4.1 that none of the components can be a tree hence the ith component
must have at least a i edges. Hence the total number of edges in the graph of calls is at least
n, contradicting the assumption on the number of calls in S. 2
Theorem 4.2 Every gossiping algorithm with running time
log
calls.
Proof: Let t be the largest integer such that less than n calls are placed before round t.
Let S  be the calling scheme consisting of all calls of S with labels at most t \Gamma 1. Lemma
4.2 implies that after time there is a node v such that jK(v)j - 2log n. (Here K(v) is
taken with respect to the calling scheme S  .) By lemma 2.2 the additional time required for
all nodes to learn the value of v is at least log n
Hence
and consequently
be the calling scheme consisting of all calls of S with labels at most t. (The number
of calls in S 1 is at least n.) Lemma 2.1 implies that after the first t rounds,
for every node v 2 X. (Here sets K \Gamma (v) are taken with respect to the calling scheme S 1 .)
consider the calling scheme S 2 consisting of the first a(n) calls
placed after round t (order calls in the same round arbitrarily). Lemma 2.1 implies that,
for every node v 2 X, taken with respect to S 2 . Thus,
upon completion of all calls in schemes S 1 and S 2 ,
for every node v 2 X.
Now at most remain to be placed. Denote by S 3 the scheme consisting of these
remaining calls. By lemma 4.2 there exists a node w, such that
now taken with respect to the scheme S 3 . It follows that upon completion of all
calls in schemes S 1 , S 2 and S 3 , i.e., at the end of the scheme S, node w knows the values of
at most
nodes. Since S is a gossiping scheme, we must have
whence
log
This concludes the proof. 2
5 Lower bounds on the number of links
In this section we establish two lower bounds on the number of links used by a gossiping
scheme with a given running time. The first bound concerns the case when the running time
is small.
Theorem 5.1 Every gossiping algorithm with running time T - log n+c log log log n, where
uses L 2 !(n(log log n) d ) links, where d
Before proving the theorem we fix some additional terminology and prove several technical
lemmas. Consider a calling scheme with running time T . Let
log log log n, c ! 1. Suppose that the number of links used by this scheme is
log log log n, for sufficiently large n. We will prove that the
considered calling scheme is not a gossiping scheme. Suppose it is.
A node v is called after round i of the scheme if jK \Gamma (v)j is at most 1
a node that
is not weak is called strong. A call between nodes v and w in round i is said to be ff-increasing
round i is at most ff times larger than
this round. Let
In every round i consider the following classes of calls:
A - Calls between weak nodes,
ffl)-increasing calls not belonging to the class A,
remaining calls.
The idea of the proof is to show that in many rounds there are few nodes that are either
or participate in calls of class C and consequently the increase of knowledge in these
rounds is too slow to enable achieving knowledge n 2 upon completion of the scheme. Among
our arguments many hold only for sufficiently large n. This does not cause any problems,
since the result is of asymptotic nature. We skip the phrase "for sufficiently large n" for the
sake of brevity.
We start with a lower bound on the number of strong nodes.
Lemma 5.1 In every round there are at least 3
strong nodes.
Proof: After every round i the knowledge K is at least because in the remaining
log rounds knowledge can increase at most 2 log n+f(n)\Gammai times and the final
knowledge must be n 2 . Let p be the number of strong nodes and the number of weak
nodes after the ith round. After the ith round the knowledge K is at most p2 i
p)2 i\Gammaf (n)\Gamma2 , hence
which implies
:The aim of the next two lemmas is to give an upper bound on the size of the class C.
Define the forbidden distance to be the maximum number k such that if a call of class C has
been placed on a link in round i then no call of this class is placed on this link in rounds
Lemma 5.2 The forbidden distance is at least 2 f(n)+b(n)+8 .
Proof: Suppose that a call of class C has been placed on link
)j be the amount of information in each of these nodes after this
round. Let l be the minimum positive integer such that a call of class C is placed on link e
in round i l. We will show that l ? 2 f(n)+b(n)+8 . Since the call on link e in round i was in
the class C, at least one of the nodes v 1 or v 2 was strong after round i \Gamma 1. Thus
Consider the increase of the number
after round 2. We have
the upper bound requiring that v j communicate in every round
having maximum and mutually disjoint information. On the other hand, jK
w after round inequality was already true after round i.
After round l we have
hence the increase of the number l is at most
In view of inequality 1 the right hand side of the above is at most
Since the call in round i+l on link e is in the class C, it is not in the class B and consequently
the number must increase in round times. Hence
we get
which implies
and finally
l
Lemma 5.3 jCj - nlog n
Proof: Since the total number of rounds is less than 2log n, there are at most 2log n
calls of class C on every link. The total number of links is at most
:The next two lemmas show that in many rounds there are many strong nodes that do not
participate in calls of class C.
Call a round essential if there are at most n
calls of class C in this round.
Lemma 5.4 At least Trounds are essential.
Proof: Otherwise more than Trounds would have more than n
calls of class C, for a
total of more than2 log n \Delta n
which contradicts lemma 5.3. 2
Lemma 5.5 In every essential round there are at least n
strong nodes that do not
participate in calls of class C.
Proof: By lemma 5.1 there are at most n(1 \Gamma 3
nodes in every round. By
definition there are at most n
calls of class C in every essential round. At most n
nodes can participate in these calls. Hence the total number of nodes that are either weak
or participate in a call of class C is at most
in every essential round. 2
The next two lemmas show that in many rounds the rate of knowledge increase can be
bounded strictly below 2.
Call a pair of nodes fv; wg red in round i if (w)j is at least 1
round sum increases at most 2 \Gamma ffl times in round i; otherwise call the pair
fv; wg white in round i.
Lemma 5.6 In every essential round there are at least n
red pairs of
nodes.
Proof: Fix an essential round i. A strong node v that does not participate in a call of class
C, either participates in a call of class B or does not communicate at all in round i. By
lemma 5.5, there are either at least n
nodes of the first type or of the second type. In
the first case there are at least n
calls in the class B because every such call involves at
least one strong node (otherwise it would be in the class A). All pairs of nodes in these calls
are red, which proves the lemma in this case. In the second case partition nodes that do not
communicate in the ith round into disjoint pairs arbitrarily. does
not increase at all in such pairs in the ith round and at least n
pairs contain a strong
node in this case, hence they are red. 2
Lemma 5.7 In every essential round the total knowledge K increases at most
times; where
Proof: For simplicity assume that the number of nodes is even, it will be clear how to
modify the argument otherwise. Fix an essential round i. By lemma 5.6 there are at least
disjoint red pairs in round i. For every such pair fv; wg,
after round and the increase of (w)j in this round is at most 2 \Gamma ffl times.
For pairs fv; wg that are white in round i, and the
increase of (w)j is at most 2 times.
We want to establish an upper bound on the rate of knowledge increase in round i. We will
compute this rate as a fraction R whose numerator is the sum of
disjoint pairs of nodes after round i and the denominator is the corresponding sum before
round i.
The value of R canot decrease if the number of red pairs is decreased to n
and the sum
lowered to 1
in every red pair, while the
number of white pairs is increased to n\Gamma n
and the sum
increased to 2 i in every white pair. Also R cannot decrease if we assume that the
increase of times in red pairs and 2 times in white pairs. Hence
we get
Denoting simplifying we get
4x
4x
and finally
. 2
Proof of theorem 5.1: Denote, as before,
. By lemmas 5.4 and
5.7, knowledge increases at most
times in at least 1log n rounds. In all remaining
rounds it increases at most 2 times. Hence in order to show that our scheme is not a gossiping
scheme it suffices to show
i.e.,
log log log n, for log log log n, for d
log n:
g(n) . The latter inequality implies h(n) - 2f(n). Since
e , we have
2:5
for sufficiently large n and thus
In view of h(n) - 2f(n) we have
which implies inequality 2. 2
The last result of this section gives a meaningful lower bound on the number of links when
the running time is in the medium or large range.
Theorem 5.2 Every gossiping algorithm with running time T - 2log
uses
log n
links.
Proof: We may assume that the
conclusion is trivial. Suppose that L -
16log n . Take a spanning tree of the underlying
graph, with root k, diameter at most 2log n and maximum degree at most 2log n. Such a
tree must exist for the gossiping to be completed in time less than 2log n. Color all links
of this tree black and all other links (at most 2 r(n)
red links to the
tree one by one, each time recoloring red those black links which appear in a newly created
cycle. If the link fv; wg is added, this causes recoloring red links on the paths joining v with
k and w with k in the tree. (Some of them may have been recolored already previously.)
Hence adding a new red link causes recoloring at most 2log n black links. After adding at
most 2 r(n)
red links, the total number of red links at the end of the recoloring process
is at most
which is less than 2 r(n)\Gamma2 for sufficiently large n, in view of
Since links that are red at the end of the recoloring process are exactly those situated in
cycles in the underlying graph, this graph has z ! 2 r(n)\Gamma2 nodes situated in cycles. Hence
there exists a tree D attached to only one node d in some cycle, such that
z
Case 1. 2n
nThe value of some node v in D reaches the node d after time larger than log 2n
1. Broadcasting the value of v from d to all nodes outside of D requires time at least
log n= log n \Gamma 1. Hence the total time of gossiping exceeds 2log
Case 2. jDj ? nSince the maximum degree of D is at most 2log n, the tree D contains a subtree Y , such
that 2n
. The rest of the argument is as in Case 1, with D replaced
by Y . 2
6 Discussion
We have two pairs of bounds on the minimum number of calls C in gossiping with a given
running time T . If ne
log
). The first pair of
bounds is useful for small t(n), e.g., when t(n) 2 O(log log n), i.e., when gossiping time is
small. They yield the following corollary showing how C gradually decreases from \Theta(nlog n)
to the asymptotically optimal range 2n + o(n), as restrictions on T are being relaxed.
Corollary 6.1 If ne
1. If t(n) is constant then C 2 \Theta(nlog n).
2. If t(n) 2 log log
3. If t(n) - log log n \Gamma d, for a constant d, then C 2 O(n).
4. If t(n) 2 log log n
The lower bound C 2 \Omega\Gamma nlog n
), following from [12], becomes trivial when t(n) ? log log n.
For even larger values of gossiping time our second pair of bounds can be applied. For
example, it gives a fairly precise estimate of the minimum number of calls when the running
time is in the medium range fflog n, 2.
Corollary 6.2 If the running time of a gossiping algorithm is
then C 2 2n +O(n 2\Gammaff log n) and C
log
The next corollary corresponds to the situation when the gossiping time is fairly large. In
this case it is more natural to reverse the problem: what is the minimum running time of
gossiping when the number of calls has to be kept very small?
Corollary 6.3 If the number of calls in a gossiping algorithm is
is polylogarithmic in n, then its running time T is 2log
Proof: Suppose not, and let
2\Omega\Gamma367 n). Then r(n) - dlog n, for
some constant d and C
log
We next turn attention to the trade-off between the time T and the number of links L. For
small values of T the gap between our upper and lower bounds is larger than in the previous
case. Corollary 3.1 and theorem 5.1 imply, for example, that if
a constant, then L 2 O(nlog n) and L 2 !(n(log log n) d ), for d ! 1. It remains open if
n) in this case.
The last pair of bounds, applicable for larger values of gossiping time
follows from corollary 3.1 and theorem 5.2. In this case L 2
log n ). For the medium range of gossiping time fflog n, gives an
even more precise estimate of L than previously of C.
Corollary 6.4 If the running time of a gossiping algorithm is
then log n) and L
log n
Finally, a result similar to corollary 6.3 holds for the number of links.
Corollary 6.5 If the number of links used by a gossiping algorithm is
c(n) is polylogarithmic in n, then its running time T is 2log
7 Conclusion
We established upper and lower bounds on the minimum number of calls and the minimum
number of links used by a gossiping scheme with a given running time. Our algorithms,
which turned out to be cost-efficient for the whole range of running time values, follow the
same simple pattern: gather information in nodes of a hypercube of appropriately chosen size
using a separate broadcasting tree for each node, then gossip in the hypercube in minimal
time and finally broadcast complete information to all remaining nodes, using again the same
broadcasting trees. The tree part of the scheme uses few calls and few links but a lot of
time, as it is executed twice, while the hypercube part is fast but uses many calls and many
links. Thus a suitable balance between these parts must be maintained to get low cost for a
given running time.
Our bounds leave very small gaps. For example, if our upper bound on C is
log n) and the lower bound is 2n
log leaving a gap within a factor of
O(log 3 n) in the part of the number of calls exceeding the absolute minimum 4. In the
case of the number of links L, our bounds are even tighter for this range of running time.
For the same value our upper bound on L is
log n) and
the lower bound is n
log n ), leaving a gap within a factor of O(log 2 n) in the part of the
number of links exceeding the absolute minimum n \Gamma 1.
Further tightening of these bounds, for all values of running time, remains a natural open
problem yielded by our results. We do not know, for example, if it is possible to gossip in
time 3log n using 2n
n) calls and/or n
n) links. It also remains open what is
the minimum value of L when const. We conjecture that L 2 \Theta(nlog n) in this
case.
Another interesting problem is to evaluate the complexity of finding the exact value of the
minimum cost of gossiping with a given running time. Given n and T , can the minimum
number of calls C or the minimum number of links L be found in polynomial time?
In many papers (cf. [4, 9, 10]) gossiping was studied for specific important networks, such as
trees, grids or hypercubes, and the time or the number of calls were minimized separately. It
would be interesting to extend our study by investigating time vs. number of calls trade-offs
in gossiping for these networks as well. Also communication models other than the classical
1-port full-duplex model (cf., e.g., [9]), could be considered in this context.



--R

Gossips and telephones
Communication patterns in task-oriented groups
A problem with telephones
Gossiping in grid graphs
Methods and problems of communication in usual net- works
Tight bounds on minimum broadcast networks
A cure for the telephone disease
A survey of gossiping and broadcasting in communication networks
Fast gossiping for the hypercube
The telephone problem for trees
Kernels of minimum size gossip schemes

Some minimum gossip graphs
The distribution of completion times for random communication in a task-oriented group
Time and call limited telephone problem
--TR

--CTR
Francis C.M. Lau , Shi-Heng Zhang, Fast Gossiping in Square Meshes/Tori with Bounded-Size Packets, IEEE Transactions on Parallel and Distributed Systems, v.13 n.4, p.349-358, April 2002
Francis C. M. Lau , S. H. Zhang, Optimal gossiping in paths and cycles, Journal of Discrete Algorithms, v.1 n.5-6, p.461-475, October
gossiping;lower bounds;algorithm