Asymptotically Optimal Randomized Rumor Spreading

DOI10.1007/978-3-642-22012-8_40zbMath1334.68029arXiv1011.1868MaRDI QIDQ3012944

Benjamin Doerr, Mahmoud Fouz

Publication date: 7 July 2011

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1011.1868

Mathematics Subject Classification ID

68M12: Network protocols

Related Items

Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication, Island models meet rumor spreading, Faster rumor spreading with multiple calls, Direction-reversing quasi-random rumor spreading with restarts, Rumor Spreading with No Dependence on Conductance

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The shortest-path problem for graphs with random arc-lengths
• Almost tight bounds for rumour spreading with conductance
• Quasirandom Rumor Spreading on the Complete Graph Is as Fast as Randomized Rumor Spreading
• Randomized broadcast in networks
• Broadcasting vs. Mixing and Information Dissemination on Cayley Graphs
• Quasirandom Rumor Spreading: Expanders, Push vs. Pull, and Robustness
• On Mixing and Edge Expansion Properties in Randomized Broadcasting
• Social networks spread rumors in sublogarithmic time
• Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems