Stochastic analysis of rumor spreading with multiple pull operations
Résumé
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$.
Origine : Fichiers produits par l'(les) auteur(s)