### Simple, Fast and Deterministic Gossip and Rumor SpreadingSimple, Fast and Deterministic Gossip and Rumor Spreading

Access Restriction
Subscribed

 Author Haeupler, Bernhard Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2015 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Gossip ♦ LOCAL model ♦ Distributed computing ♦ Information dissemination ♦ Rumor spreading Abstract We study gossip algorithms for the rumor spreading problem, which asks each node to deliver a rumor to all nodes in an unknown network. Gossip algorithms allow nodes only to call one neighbor per round and have recently attracted attention as message efficient, simple, and robust solutions to the rumor spreading problem. A long series of papers analyzed the performance of uniform random gossip in which nodes repeatedly call a random neighbor to exchange all rumors with. A main result of this investigation was that uniform gossip completes in $\textit{O}(log$ $\textit{n}/Φ)$ rounds where Φ is the conductance of the network. Nonuniform random gossip schemes were devised to allow efficient rumor spreading in networks with bottlenecks. In particular, [Censor-Hillel et al., STOC&12] gave an $O(log^{3}$ $\textit{n})$ algorithm to solve the 1-local broadcast problem in which each node wants to exchange rumors locally with its 1-neighborhood. By repeatedly applying this protocol, one can solve the global rumor spreading quickly for all networks with small diameter, independently of the conductance. All these algorithms are inherently randomized in their design and analysis. A parallel research direction has been to reduce and determine the amount of randomness needed for efficient rumor spreading. This has been done via lower bounds for restricted models and by designing gossip algorithms with a reduced need for randomness, for instance, by using pseudorandom generators with short random seeds. The general intuition and consensus of these results has been that randomization plays a important role in effectively spreading rumors and that at least a polylogarithmic number of random bit are crucially needed. In this article improves over the state of the art in several ways by presenting a $\textit{deterministic}$ gossip algorithm that solves the the $\textit{k}-local$ broadcast problem in $2(\textit{k}$ + $log_{2}$ $\textit{n})$ $log_{2}$ $\textit{n}$ rounds. Besides being the first efficient deterministic solution to the rumor spreading problem this algorithm is interesting in many aspects: It is simpler, more natural, more robust, and faster than its randomized pendant and guarantees success with certainty instead of with high probability. Its analysis is furthermore simple, self-contained, and fundamentally different from prior works. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2015-12-10 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 62 Issue Number 6 Page Count 18 Starting Page 1 Ending Page 18

#### Open content in new tab

Source: ACM Digital Library