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:Randomized Rumor Spreading Revisited
Speaker:Benjamin Doerr
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 21 April 2015
Duration:30 Minutes
Building:E1 4
Gossip-based computation is a mildly recent paradigm in distributed computing. A distributed algorithm is called gossip-based if all interaction between nodes stems from nodes calling neighbors chosen uniformly at random. This form of communication is desirable, among others, in wireless sensor networks or mobile ad-hoc networks, where the dynamic and unreliable network structure forbids more structured approaches.

In this talk, we regard the problem of communicating a single piece of information ("rumor'') from one node of the network to all other nodes. It obvious that this simple rumor spreading problem appears as subproblem of many more complicated problems. However, it is also known that many tasks can be reduced to essentially spreading a single rumor (e.g., making all nodes learn the number of nodes of the network).

We restrict ourselves to the most simple rumor spreading problem, namely the one in a complete graph (that is, each node can talk to each other; this has other applications than the ones sketched above, of course). For a broad class of synchronized rumor spreading algorithms we give a simple and uniform analysis of the rumor spreading time that is tight up to additive constants. Our result applies, among others, to push, pull, and push-pull rumor spreading including the possibility of random transmission failures. We thus reprove and strengthen some well-known results of Frieze and Grimmett, Pittel, and Karp, Scheideler, Schindelhauer, and Vocking.

A main proof idea is to not split the analysis into more and more distinct phases of (estimated) identical behavior, but instead to give a (simple) method that allows to deal with the fact that the efficiency of the process changes over time. While the results we obtain are stronger than previous works (e.g., we also derive information about the distribution of the rumor spreading time), the proofs seem to be simpler.

Name(s):Marvin Künnemann
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Created:Marvin Künnemann, 04/13/2015 05:54 PM Last modified:Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM
  • Marvin Künnemann, 04/13/2015 05:54 PM -- Created document.