Randomized Rumor Spreading

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