Continuous-Time Stochastic Analysis of Rumor Spreading with Multiple Operations

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.