Almost Optimal Randomized Rumor Spreading

Our protocol spreads a rumor from one node to all other nodes in the asymptotically optimal time of $(1 + o(1)) \log_2 n$. The whole process makes only $O(n f(n))$ calls, where $f(n)= \omega(1)$ can be arbitrary.

In spite of these quantities being close to the theoretical optima, the protocol remains relatively robust against failures. We show that for \emph{random} node failures, our algorithm again comes arbitrarily close to the theoretical optima. The protocol can be extended to also deal with \emph{adversarial} node failures. The price for this additional robustness is only a constant factor increase in the run-time, where the constant factor depends on the fraction of failing nodes the protocol is supposed to cope with.
Still only $O(n)$ calls to properly working nodes are made.
In contrast to the push-pull protocol by Karp et al. [FOCS 2000], our algorithm only uses push operations. To the best of our knowledge, this is the first randomized push algorithm that achieves an asymptotically optimal running time.

This is joint work with Benjamin Doerr. The result will also be presented at ICALP 2011.