Communication complexity of quasirandom rumor spreading

DOI10.1007/s00453-013-9861-5zbMath1322.68256OpenAlexW2104997690MaRDI QIDQ2354024

Thomas Sauerwald, Robert Elsässer, Petra Berenbrink

Publication date: 10 July 2015

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://www.repository.cam.ac.uk/handle/1810/294035

zbMATH Keywords

parallel computingrandomized algorithmbroadcasting

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Randomized algorithms (68W20)

Related Items (1)

Breaking the \(\log n\) barrier on rumor spreading

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A guided tour of Chernoff bounds
• The shortest-path problem for graphs with random arc-lengths
• Some Nonparametric Asymptotic Results for a Class of Stochastic Processes
• Almost tight bounds for rumour spreading with conductance
• Randomized broadcast in networks
• Randomised Broadcasting: Memory vs. Randomness
• Communication Complexity of Quasirandom Rumor Spreading
• Quasirandom Rumor Spreading: Expanders, Push vs. Pull, and Robustness
• On Spreading a Rumor
• Probability and Computing
• Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems

This page was built for publication: Communication complexity of quasirandom rumor spreading