Asymptotically Optimal Randomized Rumor Spreading

DOI10.1007/978-3-642-22012-8_40zbMath1334.68029arXiv1011.1868OpenAlexW1865724022MaRDI 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

Network protocols (68M12)

Related Items (5)

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

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

This page was built for publication: Asymptotically Optimal Randomized Rumor Spreading