Repository logo
 

Faster rumor spreading with multiple calls

Published version
Peer-reviewed

Loading...
Thumbnail Image

Type

Article

Change log

Authors

Panagiotou, K 
Pourmiri, A 
Sauerwald, T 

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 Θ(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.

Description

Keywords

4901 Applied Mathematics, 46 Information and Computing Sciences, 49 Mathematical Sciences, 4605 Data Management and Data Science, 4606 Distributed Computing and Systems Software

Journal Title

Electronic Journal of Combinatorics

Conference Name

Journal ISSN

0302-9743
1077-8926

Volume Title

22

Publisher

The Electronic Journal of Combinatorics