Pulling multiple nodes for rumor spreading

In this paper, 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 during a k-pull operation, an uninformed node i contacts $k − 1$ random nodes in the network, and if at least one of them knows the rumor, then node i learns it. We perform a thorough study of $T k,n ,$ the total number of k-pull operations needed for all the nodes to learn the rumor. We prove that the mean number of interactions needed for all the nodes to be informed is in $O (n ln(n)/(k − 1))$, which generalizes the standard case $k = 2$ for the push-pull, push and pull protocols. We also analyze the tail of $T k,n$ and prove that $T k,n 2$, our new protocol requires less operations than the traditional push-pull or push (resp. pull) protocols by using stochastic dominance arguments