Kolloquium Prof. Dr. Benjamin Dörr, LIX Paris: "Randomized Rumor Spreading Revisited"
LMS 4 - Raum 424 - Kleiner Hörsaal.
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