Randomized rumor spreading

We investigate the class of so-called epidemic algorithms that are commonly \nused for the lazy transmission of\nupdates to distributed copies of a database. These algorithms use a simple \nrandomized communication\nmechanism to ensure robustness. Suppose $n$ players communicate in parallel \nrounds in each of which every\nplayer calls a randomly selected communication partner. In every round, players \ncan generate rumors\n(updates) that are to be distributed among all players. Whenever communication \nis established between two\nplayers, each one must decide which of the rumors to transmit. The major \nproblem (arising due to the\nrandomization) is that players might not know which rumors their partners have \nalready received. For\nexample, a standard algorithm forwarding each rumor from the calling to the \ncalled players for $\\Theta(\\ln\nn)$ rounds needs to transmit the rumor $\\Theta(n \\ln n)$ times in order to \nensure that every player finally\nreceives the rumor with high probability. \n\nWe investigate whether such a large communication overhead is inherent to \nepidemic algorithms. On the\npositive side, we show that the communication overhead can be reduced \nsignificantly. We give an algorithm\nusing only $O(n \\ln\\ln n)$ transmissions and $O(\\ln n)$ rounds. In addition, we \nprove the robustness of this\nalgorithm, e.g., against adversarial failures. On the negative side, we show \nthat any address-oblivious algorithm\n(i.e., an algorithm that does not use the addresses of communication partners) \nneeds to send $\\Omega(n \\ln\\ln\nn)$ messages for each rumor regardless of the number of rounds. Furthermore, we \ngive a general lower bound\nshowing that time- and communication-optimality cannot be achieved \nsimultaneously using random phone\ncalls, that is, every algorithm that distributes a rumor in $O(\\ln n)$ rounds \nneeds $\\omega(n)$ transmissions.