Continuous-time stochastic analysis of rumor spreading with multiple operations
Authors:
- Bruno SericolaBSBruno Sericola
- Emmanuelle AnceaumeEAEmmanuelle Anceaume
- Yves MocquardYMYves Mocquard
Preprint
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 ≥ 2, and called k-pull operations. Specifically during a k-pull operation, an uninformed node a contacts 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 Θ 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 Θ k,n together with their asymptotic behavior when the number of nodes n tends to infinity.Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- Stochastic Analysis of Rumor Spreading with Multiple Pull OperationsMethodology and Computing in Applied Probability, 2021
- On the Push&Pull Protocol for Rumour Spreading2017
- Rumor spreading in random evolving graphsRandom Structures & Algorithms, 2015
- Randomized Rumour Spreading: The Effect of the Network TopologyCombinatorics, Probability and Computing, 2014
- Rumor spreading on random regular graphs and expandersRandom Structures & Algorithms, 2012
- Experimental Analysis of Rumor Spreading in Social NetworksLecture Notes in Computer Science, 2012
- Rumor spreading in social networksTheoretical Computer Science, 2011
- A pull model IPv6 Duplicate Address Detection2010
- On Spreading a RumorSIAM Journal on Applied Mathematics, 1987
- Epidemic Modelling1984