Randomized broadcast in networks

DOI10.1002/RSA.3240010406zbMath0712.68011OpenAlexW2047784567MaRDI QIDQ3197297

Eli Upfal, Prabhakar Raghavan, David Peleg

Publication date: 1990

Published in: Random Structures and Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.3240010406

zbMATH Keywords

random graphs randomized algorithms undirected graph rumor propagation distributed computation broadcast protocols maintenance of replicated databases

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Network design and communication in computer systems (68M10) Applications of graph theory to circuits and networks (94C15)

Related Items (63)

On fast and robust information spreading in the vertex-congest model ⋮ On optimal broadcasting in faulty hypercubes ⋮ On the runtime and robustness of randomized broadcasting ⋮ On the number of broadcast schemes in networks ⋮ On mixing and edge expansion properties in randomized broadcasting ⋮ Stochastic analysis of rumor spreading with multiple pull operations ⋮ Agent-based randomized broadcasting in large networks ⋮ The Weighted Coupon Collector’s Problem and Applications ⋮ Diameter and broadcast time of random geometric graphs in arbitrary dimensions ⋮ Information Spreading in a Large Population of Active Transmitters and Passive Receivers ⋮ Randomised broadcasting: memory vs. randomness ⋮ On the Push&Pull Protocol for Rumor Spreading ⋮ Rumors Spread Slowly in a Small-World Spatial Network ⋮ Stateless Information Dissemination Algorithms ⋮ Push is Fast on Sparse Random Graphs ⋮ Continuous-time stochastic analysis of rumor spreading with multiple operations ⋮ Deterministic broadcasting time with partial knowledge of the network. ⋮ Messy broadcasting - decentralized broadcast schemes with limited knowledge ⋮ Rumor Spreading with No Dependence on Conductance ⋮ Randomized Rumour Spreading: The Effect of the Network Topology ⋮ An analytical model for multi-epidemic information dissemination ⋮ Asymptotics for pull on the complete graph ⋮ Direction-reversing quasi-random rumor spreading with restarts ⋮ Order optimal information spreading using algebraic gossip ⋮ Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems ⋮ On Mixing and Edge Expansion Properties in Randomized Broadcasting ⋮ On linear-time data dissemination in dynamic rooted trees ⋮ Probabilistic Analysis of Rumor-Spreading Time ⋮ Parsimonious flooding in dynamic graphs ⋮ The String of Diamonds Is Tight for Rumor Spreading ⋮ Analysis of randomized protocols for conflict-free distributed access ⋮ Asymptotic bounds on the equilateral dimension of hypercubes ⋮ Asymptotically Optimal Randomized Rumor Spreading ⋮ Broadcasting on cactus graphs ⋮ Efficient communication in unknown networks ⋮ Faster rumor spreading with multiple calls ⋮ Rumor spreading in social networks ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Radio communication in random graphs ⋮ Broadcast in the rendezvous model ⋮ Unnamed Item ⋮ Efficient Broadcasting in Random Power Law Networks ⋮ Rumor spreading in random evolving graphs ⋮ Broadcasting in weighted trees under the postal model ⋮ On randomized broadcasting in star graphs ⋮ Asymptotics for push on the complete graph ⋮ Rumor spreading with bounded in-degree ⋮ Randomized rumor spreading in poorly connected small-world networks ⋮ Introducing Quasirandomness to Computer Science ⋮ On broadcasting in unicyclic graphs ⋮ Asynchronous Broadcasting with Bivalent Beeps ⋮ Sparsifying Congested Cliques and Core-Periphery Networks ⋮ Time-Efficient Broadcast in Radio Networks ⋮ Sub-linear Universal Spatial Gossip Protocols ⋮ Breaking the \(\log n\) barrier on rumor spreading ⋮ The string of diamonds is nearly tight for rumour spreading ⋮ Robustness of randomized rumour spreading ⋮ Quasirandom Rumor Spreading on Expanders ⋮ Quasirandom broadcasting on the complete graph is as fast as randomized broadcasting ⋮ Rumor spreading on random regular graphs and expanders ⋮ Unnamed Item ⋮ Communication complexity of quasirandom rumor spreading

This page was built for publication: Randomized broadcast in networks