Campus Event Calendar
Event Entry
What and Who
On Quasirandom Rumor Spreading
Anna Huber
Max-Planck-Institut für Informatik - D1
Ringvorlesung
AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, MMCI
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 15 January 2009
13:00
60 Minutes
E1 3 - Hörsaal Gebäude
0.16
Saarbrücken
Abstract
Randomized rumor spreading is a protocol for disseminating information
in a network. The problem is as follows. Initially, one vertex of a
finite, undirected connected graph has some piece of information
(``rumor''). Each round, each vertex knowing the rumor tells it to a
neighbor chosen uniformly at random (resulting in that this vertex now
also knows the rumor and starts gossiping in the next round). The
question is how many rounds are necessary to inform all vertices of the
graph with high probability. Results of Frieze and Grimmett show that in
a complete graph on $n$ vertices, this simple protocol succeeds in
spreading the rumor from one node to all others within $(1 +
o(1))(\log_2(n) + \ln(n))$ rounds.
Benjamin Doerr, Tobias Friedrich and Thomas Sauerwald proposed a
quasirandom analogue of the randomized rumor spreading model. Here, each
vertex has a cyclic permutation of its neighbors. When first passing the
rumor, it chooses a neighbor uniformly at random. All subsequent
gossiping is done to the successors of this vertex in the cyclic
permutation. For complete graphs, hypercubes and a broader range of
random graphs it was then shown that, independent of the choice of the
cyclic permutations, this protocol also needs $O(\log n)$ rounds only to
inform all other nodes. We show that for complete graphs we do not even
lose a constant factor, that is, independent of the cyclic permutations,
the protocol informs all nodes in $(1 + o(1)) (\log_2(n) + \ln(n))$ rounds.
This is joint work with Benjamin Doerr.
in a network. The problem is as follows. Initially, one vertex of a
finite, undirected connected graph has some piece of information
(``rumor''). Each round, each vertex knowing the rumor tells it to a
neighbor chosen uniformly at random (resulting in that this vertex now
also knows the rumor and starts gossiping in the next round). The
question is how many rounds are necessary to inform all vertices of the
graph with high probability. Results of Frieze and Grimmett show that in
a complete graph on $n$ vertices, this simple protocol succeeds in
spreading the rumor from one node to all others within $(1 +
o(1))(\log_2(n) + \ln(n))$ rounds.
Benjamin Doerr, Tobias Friedrich and Thomas Sauerwald proposed a
quasirandom analogue of the randomized rumor spreading model. Here, each
vertex has a cyclic permutation of its neighbors. When first passing the
rumor, it chooses a neighbor uniformly at random. All subsequent
gossiping is done to the successors of this vertex in the cyclic
permutation. For complete graphs, hypercubes and a broader range of
random graphs it was then shown that, independent of the choice of the
cyclic permutations, this protocol also needs $O(\log n)$ rounds only to
inform all other nodes. We show that for complete graphs we do not even
lose a constant factor, that is, independent of the cyclic permutations,
the protocol informs all nodes in $(1 + o(1)) (\log_2(n) + \ln(n))$ rounds.
This is joint work with Benjamin Doerr.
Contact
imprs
225
--email hidden
passcode not visible
logged in users only
Jennifer Gerling, 01/13/2009 10:55 -- Created document.