# Kolloquium Prof. Dr. Benjamin Dörr, LIX Paris: "Randomized Rumor Spreading Revisited"

Oct 21, 2016 from 04:45 PM to 05:45 PM

Abstract:

Randomized rumor spreading is a simple round-based process to disseminate a piece of information

(``rumor'') in a network. We assume that initially a single node knows the rumor. Then in each

round of the process, each informed node simultaneously contacts a random neighbor and informs it.

The rumor spreading time is the number of rounds it takes to have all nodes informed. A number of

variations of this process have been studied. For example, we can alternatively assume that in each

round, each node (regardless of being informed or not) contacts a random neighbor with the result

that if one of the two nodes was informed, then also the other node becomes informed. We can also

assume that the communication is not very reliable, that is, that each communication attempt fails

with a certain probability.

While studied intensively in the literature, so far even the most basic setting that each node can

communicate with each other (complete graph) was not too well understood. In particular, each

of the many variants of rumor spreading needed a separate mathematical analysis. In this work,

we overcome this difficulty. We distill a small number of simple properties that suffice to prove

expected rumor spreading times that are tight apart from additive constants. Interestingly, and

in contrast to previous works, the proofs of these results are elementary and need nothing

beyond Chebyshev's inequality.

Einladender: Herr Gnewuch