AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI   Info

AG Audience

English

30 Minutes

Saarbrücken

We consider the random phone call model (also known as randomized rumor spreading) introduced by Karp et al. (FOCS'00), which is a well-studied epidemic protocol for spreading information from one node to all n nodes of a network. One basic variant called Push protocol proceeds in rounds and in each round every informed node calls a random neighbor and informs it of the rumor. The Push-Pull protocol works similarly, but additionally in each round also every uninformed node calls a random neighbor and may learn the rumor from that neighbor. While it is well-known that both protocols need \Theta(log n) rounds to spread a rumor on a complete network with n nodes, we are interested by how much we can speed up the spread of the rumor 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 u is chosen independently according to a probability distribution R with bounded mean determined at the beginning of the process. 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 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.

Ali Pourmiri

--email hidden

passcode not visible

logged in users only