Skip to Main content Skip to Navigation
Journal articles

Stochastic analysis of rumor spreading with $k$-pull operations

Frédérique Robin 1 Bruno Sericola 2 Emmanuelle Anceaume 1 Yves Mocquard 3
1 CIDRE - Confidentialité, Intégrité, Disponibilité et Répartition
CentraleSupélec, Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
2 DIONYSOS - Dependability Interoperability and perfOrmance aNalYsiS Of networkS
3 MINGUS - Multi-scale numerical geometric schemes
IRMAR - Institut de Recherche Mathématique de Rennes, ENS Rennes - École normale supérieure - Rennes, Inria Rennes – Bretagne Atlantique
Abstract : We propose and analyze a new asynchronous rumor spreading protocol to deliver a rumor to all the nodes of a large-scale distributed network. This spreading protocol relies on what we call a $k$-pull operation, with $k \geq 2$. Specifically a $k$-pull operation consists, for an uninformed node $s$, in contacting $k-1$ other nodes at random in the network, and if at least one of them knows the rumor, then node $s$ learns it. We perform a thorough study of the total number $T_{k,n}$ of $k$-pull operations needed for all the $n$ nodes to learn the rumor. We compute the expected value and the variance of $T_{k,n}$, together with their limiting values when $n$ tends to infinity. We also analyze the limiting distribution of $(T_{k,n} - E(T_{k,n}))/n$ and prove that it has a double exponential distribution when $n$ tends to infinity. Finally, we show that when $k > 2$, our new protocol requires less operations than the traditional $2$-push-pull and $2$-push protocols by using stochastic dominance arguments. All these results generalize the standard case $k=2$.
Complete list of metadata
Contributor : Emmanuelle Anceaume Connect in order to contact the contributor
Submitted on : Monday, November 22, 2021 - 8:47:00 AM
Last modification on : Friday, January 21, 2022 - 3:12:01 AM


Files produced by the author(s)


  • HAL Id : hal-03128118, version 2


Frédérique Robin, Bruno Sericola, Emmanuelle Anceaume, Yves Mocquard. Stochastic analysis of rumor spreading with $k$-pull operations. Methodology and Computing in Applied Probability, Springer Verlag, 2021. ⟨hal-03128118v2⟩



Les métriques sont temporairement indisponibles