Stochastic Analysis of Rumor Spreading with Multiple Pull Operations

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 .