Randomized Rumor Spreading Revisited (11:20–12:05)

Benjamin Doerr ( École Polytechnique de Paris )

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.