Analysis of Rumor Spreading with 2-pull or 3-pull Operations

In this paper, we analyze a new asynchronous rumor spreading protocol to deliver a rumor to all the nodes of a large-scale distributed network. This protocol relies on successive pull operations involving
$k$
different nodes, with
$k=2$
or
$k=3$
, and called
$k$
-pull operations. Specifically during a k-pull operation, an uninformed node
$a$
contacts
$k-1$
other nodes at random in the network, and if at least one of them knows the rumor, then node
$a$
learns it. We perform a detailed study in continuous-time of
$\Theta_{k, n}$
, the total time needed for all the
$n$
nodes to learn the rumor. We obtain, for
$k\in\{2,3\}$
, the mean value, the variance and the distribution of
$\Theta_{k, n}$
together with their asymptotic behavior when the number of nodes
$n$
tends to infinity.