文章基本信息

标题：The String of Diamonds Is Tight for Rumor Spreading
本地全文：下载
作者：Omer Angel ; Abbas Mehrabian ; Yuval Peres 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：81
页码：26:1-26:9
DOI：10.4230/LIPIcs.APPROX-RANDOM.2017.26
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：randomized rumor spreading; push&pull protocol; asynchronous time model; string of diamonds