2026-07-23T18:55:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7575 2024-03-06T10:40:39Z ddc:004 open_access

The String of Diamonds Is Tight for Rumor Spreading Angel, Omer Mehrabian, Abbas Peres, Yuval randomized rumor spreading push&pull protocol asynchronous time model string of diamonds For a rumor spreading protocol, the spread time is defined as the first time that everyone learns the rumor. We compare the synchronous push&pull rumor spreading protocol with its asynchronous variant, and show that for any n-vertex graph and any starting vertex, the ratio between their expected spread times is bounded by O(n^{1/3} log^{2/3} n). This improves the O(sqrt n) upper bound of Giakkoupis, Nazari, and Woelfel (in Proceedings of ACM Symposium on Principles of Distributed Computing, 2016). Our bound is tight up to a factor of O(log n), as illustrated by the string of diamonds graph. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Omer Angel and Abbas Mehrabian and Yuval Peres 2017 Is Part Of LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2017.26 urn:nbn:de:0030-drops-75754 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.26 eng https://creativecommons.org/licenses/by/3.0/legalcode