Continuous-time stochastic analysis of rumor spreading with multiple operations

François Castella (1) , Bruno Sericola (2) , Emmanuelle Anceaume (3) , Yves Mocquard (1)

1 MINGUS - Multi-scale numerical geometric schemes
2 ERMINE - mEasuRing and ManagIng Network operation and Economic
3 CIDRE - Confidentialité, Intégrité, Disponibilité et Répartition

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.

Mots clés: Rumor spreading time; k-pull protocol; Poisson Process; Markov chain; Asymptotic analysis

Domaines: Informatique [cs]; Algorithme et structure de données [cs.DS]; Calcul parallèle, distribué et partagé [cs.DC]

François Castella, Bruno Sericola, Emmanuelle Anceaume, Yves Mocquard. Continuous-time stochastic analysis of rumor spreading with multiple operations. 2022. ⟨hal-03681995⟩