@article{PanagiotouEJC2015,
TITLE = {Faster Rumor Spreading with Multiple Calls},
AUTHOR = {Panagiotou, Konstantinos and Pourmiri, Ali and Sauerwald, Thomas},
LANGUAGE = {eng},
ISSN = {1077-8926},
URL = {http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p23},
PUBLISHER = {N.J. Calkin and H.S. Wilf},
ADDRESS = {Atlanta, Ga.},
YEAR = {2015},
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.},
JOURNAL = {The Electronic Journal of Combinatorics},
VOLUME = {22},
NUMBER = {1},
EID = {P1.23},
}