# Item

ITEM ACTIONSEXPORT

Released

Journal Article

#### Faster Rumor Spreading with Multiple Calls

##### MPS-Authors

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

There are no public fulltexts stored in PuRe

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Panagiotou, K., Pourmiri, A., & Sauerwald, T. (2015). Faster Rumor Spreading with
Multiple Calls.* The Electronic Journal of Combinatorics,* *22*(1):
P1.23. Retrieved from http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p23.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0025-758E-5

##### Abstract

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 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 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 beta is an element of (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(log n/log log n) rounds.