Skip to Main content Skip to Navigation
Journal articles

The worst case behavior of randomized gossip protocols

Abstract : This paper considers the quasi-random rumor spreading model introduced by Doerr, Friedrich, and Sauerwald in [10], hereafter referred to as the list-based model. Each node is provided with a cyclic list of all its neighbors, and, upon reception of a message, it chooses a random position in its list, and from then on calls its neighbors in the order of the list. This model is known to perform asymptotically at least as well as the random phone-call model, for many network classes. Motivated by potential applications of the list-based model to live streaming, we are interested in its worst case behavior. Our first main result is the design of an 0 (m + n logn)-time algorithm that, given any n-node m-edge network G, and any source-target pair s, t is an element of V (G), computes the maximum number of rounds it may take for a rumor to be broadcast from s to t in G, in the list-based model. Hence, the list-based model is computationally easy to tackle in its basic version. The situation is radically different when one is considering variants of the model in which nodes are aware of the status of their neighbors, i.e., are aware of whether or not they have already received the rumor, at any point in time. Indeed, our second main result states that, unless P = NP, the worst case behavior of the list-based model with the additional feature that every node is perpetually aware of which of its neighbors have already received the rumor cannot be approximated in polynomial time within a (1/n)(1/2-epsilon) multiplicative factor, for any epsilon > 0. As a byproduct of this latter result, we can show that, unless P = NP, there are no PTAS enabling to approximate the worst case behavior of the list-based model, whenever every node perpetually keeps track of the subset of its neighbors which have sent the rumor to it so far.
Document type :
Journal articles
Complete list of metadata
Contributor : Pierre Fraigniaud Connect in order to contact the contributor
Submitted on : Monday, January 12, 2015 - 10:15:15 AM
Last modification on : Wednesday, February 23, 2022 - 3:17:52 PM

Links full text




Hervé Baumann, Pierre Fraigniaud, Hovhannes A. Harutyunyan, Rémi de Verclos. The worst case behavior of randomized gossip protocols. Theoretical Computer Science, Elsevier, 2014, 560 (Part2), pp.108-120. ⟨10.1016/j.tcs.2014.08.008⟩. ⟨hal-01102113⟩



Record views