Skip to Main content Skip to Navigation

Precise Analysis of Epidemic Algorithms

Abstract : Epidemic algorithms are distributed algorithms in which the agents in thenetwork involve peers similarly to the spread of epidemics. In this work, we focus on randomized rumor spreading -- a class of epidemic algorithms based on the paradigm that nodes call random neighbors and exchange information with these contacts. Randomized rumor spreading has found numerous applications from the consistency maintenance of replicated databases to newsspreading in social networks. Numerous mathematical analyses of different rumor spreading algorithms can be found in the literature. Some of them provide extremely sharp estimates for the performance of such processes, but most of them are based on the inherent properties of concrete algorithms.We develop new simple and generic method to analyze randomized rumor spreading processes in fully connected networks. In contrast to all previous works, which heavily exploit the precise definition of the process under investigation, we only need to understand the probability and the covariance of the events that uninformed nodes become informed. This universality allows us to easily analyze the classic push, pull, and push-pull protocols both in their pure version and in several variations such as when messages fail with constant probability or when nodes call a random number of others each round. Some dynamic models can be analyzed as well, e.g., when the network is a random graph sampled independently each round [Clementi et al. (ESA 2013)]. Despite this generality, our method determines the expected rumor spreading time precisely apart from additive constants, which is more precise than almost all previous works. We also prove tail bounds showing that a deviation from the expectation by more than an additive number of r rounds occurs with probability at most exp(−Ω(r)).We further use our method to discuss the common assumption that nodes can answer any number of incoming calls. We observe that the restriction that only one call can be answered leads to a significant increase of the runtime of the push-pull protocol. In particular, the double logarithmic end phase of the process now takes logarithmic time. This also increases the message complexity from the asymptotically optimal Θ(n log log n) [Karp, Shenker, Schindelhauer, Vöcking (FOCS 2000)] to Θ(n log n). We propose a simple variation of the push-pull protocol that reverts back to the double logarithmic end phase and thus to the Θ(n log log n) message complexity.
Document type :
Complete list of metadatas

Cited literature [55 references]  Display  Hide  Download
Contributor : Abes Star :  Contact
Submitted on : Thursday, November 9, 2017 - 9:26:07 PM
Last modification on : Sunday, February 2, 2020 - 1:20:41 PM
Long-term archiving on: : Saturday, February 10, 2018 - 2:42:05 PM


Version validated by the jury (STAR)


  • HAL Id : tel-01632253, version 1


Anatolii Kostrygin. Precise Analysis of Epidemic Algorithms. Other [cs.OH]. Université Paris-Saclay, 2017. English. ⟨NNT : 2017SACLX042⟩. ⟨tel-01632253⟩



Record views


Files downloads