Stochastic Analysis of Rumor Spreading with Multiple Pull Operations

Frédérique Robin (), Bruno Sericola (), Emmanuelle Anceaume () and Yves Mocquard ()
Additional contact information
Frédérique Robin: Inria, Univ. Rennes, CNRS, IRISA Inria, Campus de Beaulieu
Bruno Sericola: Inria, Univ. Rennes, CNRS, IRISA Inria, Campus de Beaulieu
Emmanuelle Anceaume: CNRS, Univ. Rennes, Inria, IRISA IRISA, Campus de Beaulieu
Yves Mocquard: Inria, Univ. Rennes, CNRS, IRISA Inria, Campus de Beaulieu

Methodology and Computing in Applied Probability, 2022, vol. 24, issue 3, 2195-2211

Abstract: 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 \ge 2$$ k ≥ 2 . Specifically a k-pull operation consists, for an uninformed node s, in contacting $$k-1$$ 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}$$ 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}$$ 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$$ ( 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$$ 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$$ k = 2 .

Keywords: Rumor spreading; Pull protocol; Markov chain; Asymptotic analysis; 68R99 (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s11009-021-09911-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:metcap:v:24:y:2022:i:3:d:10.1007_s11009-021-09911-4

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/11009

DOI: 10.1007/s11009-021-09911-4

Access Statistics for this article

Methodology and Computing in Applied Probability is currently edited by Joseph Glaz

More articles in Methodology and Computing in Applied Probability from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().