Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:On Quasirandom Rumor Spreading
Speaker:Anna Huber
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Friday, 19 September 2008
Duration:30 Minutes
Building:E1 4
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 gossipping 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 gossipping 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.

Joint work with Benjamin Doerr.

Name(s):Anna Huber
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Anna Huber, 09/08/2008 10:34 PM -- Created document.