Stochastic analysis of rumor spreading with $k$-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 \geq 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,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}$, 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$ 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$.