Faster rumor spreading with multiple calls (Q2256120)

Summary: We consider the random phone call model introduced by Demers et al., which is a well-studied model for information dissemination on networks. One basic protocol in this model is the so-called Push protocol which 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 \(\Theta(\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 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 \(\beta \in (2,3)\), we show that the Push-Pull protocol spreads a rumor in \(\Theta(\log \log n)\) rounds. Moreover when \(\beta=3\), the Push-Pull protocol spreads a rumor in \(\Theta(\frac{ \log n}{\log\log n})\) rounds.