Continuous-Time Stochastic Analysis of Rumor Spreading with Multiple Operations

François Castella (), Bruno Sericola (), Emmanuelle Anceaume () and Yves Mocquard ()
Additional contact information
François Castella: University of Rennes
Bruno Sericola: Inria
Emmanuelle Anceaume: CNRS
Yves Mocquard: Inria

Methodology and Computing in Applied Probability, 2023, vol. 25, issue 4, 1-21

Abstract: Abstract In this paper, we analyze a new asynchronous rumor spreading protocol to deliver a rumor to all the nodes of a large-scale distributed network. This protocol relies on successive pull operations involving k different nodes, with $$k\ge 2$$ k ≥ 2 , and called k-pull operations. Specifically during a k-pull operation, an uninformed node a contacts $$k-1$$ k - 1 other nodes at random in the network, and if at least one of them knows the rumor, then node a learns it. We perform a detailed study in continuous-time of the total time $$\Theta _{k,n}$$ Θ k , n needed for all the n nodes to learn the rumor. These results extend those obtained in a previous paper which dealt with the discrete-time case. We obtain the mean value, the variance and the distribution of $$\Theta _{k,n}$$ Θ k , n together with their asymptotic behavior when the number of nodes n tends to infinity.

Keywords: Rumor spreading time; k-pull protocol; Poisson Process; Markov chain; Asymptotic analysis; 60J27; 65J40 (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s11009-023-10058-7 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:25:y:2023:i:4:d:10.1007_s11009-023-10058-7

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

DOI: 10.1007/s11009-023-10058-7

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 ().