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 >= 2. Specifically a k-pull operation consists, for an uninformed node s, in contacting 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,T-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,T-n, together with their limiting values when n tends to infinity. We also analyze the limiting distribution of (T-k,T-n - E(T-k,T-n))/n and prove that it has a double exponential distribution when n tends to infinity. Finally, we show that when 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.