Hilfe Wegweiser Impressum Kontakt Einloggen





Randomized Rumor Spreading


Vöcking,  Berthold
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar

Karp, R., Schindelhauer, C., Shenker, S., & Vöcking, B. (2000). Randomized Rumor Spreading. In 41th Annual Symposium on Foundations of Computer Science (FOCS-00) (pp. 565-574). Washington, USA: IEEE.

We investigate the class of so-called epidemic algorithms that are commonly used for the lazy transmission of updates to distributed copies of a database. These algorithms use a simple randomized communication mechanism to ensure robustness. Suppose $n$ players communicate in parallel rounds in each of which every player calls a randomly selected communication partner. In every round, players can generate rumors (updates) that are to be distributed among all players. Whenever communication is established between two players, each one must decide which of the rumors to transmit. The major problem (arising due to the randomization) is that players might not know which rumors their partners have already received. For example, a standard algorithm forwarding each rumor from the calling to the called players for $\Theta(\ln n)$ rounds needs to transmit the rumor $\Theta(n \ln n)$ times in order to ensure that every player finally receives the rumor with high probability. We investigate whether such a large communication overhead is inherent to epidemic algorithms. On the positive side, we show that the communication overhead can be reduced significantly. We give an algorithm using only $O(n \ln\ln n)$ transmissions and $O(\ln n)$ rounds. In addition, we prove the robustness of this algorithm, e.g., against adversarial failures. On the negative side, we show that any address-oblivious algorithm (i.e., an algorithm that does not use the addresses of communication partners) needs to send $\Omega(n \ln\ln n)$ messages for each rumor regardless of the number of rounds. Furthermore, we give a general lower bound showing that time- and communication-optimality cannot be achieved simultaneously using random phone calls, that is, every algorithm that distributes a rumor in $O(\ln n)$ rounds needs $\omega(n)$ transmissions.