Faster rumor spreading with multiple calls
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.
- Almost tight bounds for rumour spreading with conductance
- Asymptotically optimal randomized rumor spreading
- Asynchronous Rumor Spreading in Preferential Attachment Graphs
- Concentration of Measure for the Analysis of Randomized Algorithms
- Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems
- Fast Distributed Algorithms for Computing Separable Functions
- scientific article; zbMATH DE number 5454133 (Why is no real title available?)
- scientific article; zbMATH DE number 5764878 (Why is no real title available?)
- scientific article; zbMATH DE number 6783404 (Why is no real title available?)
- MANETS: High Mobility Can Make Up for Low Transmission Power
- On Spreading a Rumor
- On the Runtime and Robustness of Randomized Broadcasting
- On the spread of viruses on the Internet
- Partial information spreading with application to distributed maximum coverage
- Probabilistic methods for algorithmic discrete mathematics
- Randomized broadcast in networks
- Resource discovery in distributed networks
- Rumor spreading and vertex expansion
- Rumor Spreading in Social Networks
- Rumor spreading on random regular graphs and expanders
- Social networks spread rumors in sublogarithmic time
- The shortest-path problem for graphs with random arc-lengths
- Tight bounds for rumor spreading in graphs of a given conductance
- Ultra-fast rumor spreading in social networks
- On linear-time data dissemination in dynamic rooted trees
- Breaking the \(\log n\) barrier on rumor spreading
- Stochastic analysis of rumor spreading with multiple pull operations
- Randomized rumor spreading in poorly connected small-world networks
- Faster rumor spreading with multiple calls
- Quick Gossiping by Conference Calls
- How to Spread Rumors Fast
- Theory and practice of discrete interacting agents models
- Randomized rumor spreading revisited
- How to Spread a Rumor
- Social networks spread rumors in sublogarithmic time
- Ultra-fast rumor spreading in social networks
- Continuous-time stochastic analysis of rumor spreading with multiple operations
- Rumors with changing credibility
This page was built for publication: Faster rumor spreading with multiple calls
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2256120)
