Communication complexity of quasirandom rumor spreading

DOI10.1007/S00453-013-9861-5MaRDI QIDQ2354024zbMATH OpenOpenAlexFDO

Authors Petra Berenbrink, Robert Elsässer, Thomas Sauerwald

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

randomized algorithmparallel computingbroadcasting

Mathematics Subject Classification ID

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

Recommendations

• Communication complexity of quasirandom rumor spreading
• Quasirandom rumor spreading
• Quasirandom Rumor Spreading: An Experimental Analysis
• Quasirandom rumor spreading, an experimental analysis
• Tight bounds for quasirandom rumor spreading

Cites work

• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 4170917 (Why is no real title available?)
• scientific article; zbMATH DE number 5764860 (Why is no real title available?)
• scientific article; zbMATH DE number 5764878 (Why is no real title available?)
• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• A guided tour of Chernoff bounds
• Almost tight bounds for rumour spreading with conductance
• Communication complexity of quasirandom rumor spreading
• Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems
• On Spreading a Rumor
• Probability and Computing
• Quasirandom Rumor Spreading: Expanders, Push vs. Pull, and Robustness
• Randomised Broadcasting: Memory vs. Randomness
• Randomized broadcast in networks
• Some nonparametric asymptotic results for a class of stochastic processes
• The shortest-path problem for graphs with random arc-lengths
• Tight bounds for rumor spreading in graphs of a given conductance

Cited in

(2)

• Communication complexity of quasirandom rumor spreading
• Breaking the \(\log n\) barrier on rumor spreading

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2354024)