Faster rumor spreading with multiple calls

We consider the random phone call model introduced by Demers et al., which is a well-studied model for information dissemination in networks. One basic protocol in this model is the so-called Push protocol that proceeds in synchronous rounds. Starting with a single node which knows of a rumor, every informed node calls in each round a random neighbor and informs it of the rumor. The Push-Pull protocol works similarly, but additionally every uninformed node calls a random neighbor and may learn the rumor from it. It is well-known that both protocols need Θ(log n) rounds to spread a rumor on a complete network with n nodes. Here we are interested in how much the spread can be speeded up by enabling nodes to make more than one call in each round. We propose a new model where the number of calls of a node is chosen independently according to a probability distribution R. We provide both lower and upper bounds on the rumor spreading time depending on statistical properties of R such as the mean or the variance (if they exist). In particular, if R follows a power law distribution with exponent β ∈ (2, 3), we show that the Push-Pull protocol spreads a rumor in Θ(log log n) rounds. Moreover, when β = 3, the Push- Pull protocol spreads a rumor in Θ(formula presented) rounds