View/hide extracted text (may have errors)
Simple, Fast and Deterministic Gossip and Rumor Spreading Bernhard Haeupler* Abstract its randomized pendant and guarantees success with We study gossip algorithms for the rumor spreading certainty instead of with high probability. Its analysis problem which asks each node to deliver a rumor to is furthermore simple, self-contained and fundamentally all nodes in an unknown network. Gossip algorithms different from prior works. allow nodes only to call one neighbor per round and have recently attracted attention as message efficient, simple 1 Introduction and robust solutions to the rumor spreading problem. Broadcasting, that is, disseminating information A long series of papers analyzed the performance of present initially at different nodes in an unknown net- uniform random gossip in which nodes repeatedly call a work to every node, is a fundamental network commu- random neighbor to exchange all rumors with. A main nication primitive with many applications. It has been result of this investigation was that uniform gossip com- studied under different names such as gossip, rumor pletes in O( log n ) rounds where Φ is the conductance spreading, information dissemination, (all-to-all) mul- of the network. More recently, non-uniform random ticast or (global) broadcast.Φ gossip schemes were devised to allow efficient rumor Gossip algorithms during which nodes contact or spreading in networks with bottlenecks. In particular, call only one neighbor at a time have been proposed [Censor-Hillel et al., STOC’12] gave an O(log3 n) algo- as a powerful time and message efficient alternatives rithm to solve the 1-local broadcast problem in which to flooding, i.e., repeatedly forwarding information to each node wants to exchange rumors locally with its all neighbors, or structured broadcast protocols which 1-neighborhood. By repeatedly applying this protocol often require a stable network with known topology. one can solve the global rumor spreading quickly for The simplest and most widely studied form of gossip all networks with small diameter, independently of the is uniform (random) gossip in which nodes repeatedly conductance. call a random neighbor to exchange information. A All these algorithms are inherently randomized in series of results showed that this algorithm performs their design and analysis. A parallel research direction well on well-connected graphs with no bottleneck(s) [5, has been to reduce and determine the amount of ran- 6,11,12,19]. More precisely, the main result is a tight domness needed for efficient rumor spreading. This has bound of O( log n ) rounds, where Φ is the conductance of been done via lower bounds for restricted models and by the network. More recently, non-uniform random gossipΦ designing gossip algorithms with a reduced need for ran- schemes were devised to allow efficient rumor spreading domness, e.g., by using pseudorandom generators with in arbitrary networks [3,4]. The local broadcast problem, short random seeds. The general intuition and consen- that asks each node to exchange rumors locally with sus of these results has been that randomization plays a all its neighbors, has been a crucial abstraction to important role in effectively spreading rumors and that obtain results independent from any conductance-type at least a polylogarithmic number of random bit are measure. In particular, building on the results on crucially needed. uniform gossip it was shown in [3] how to solve the local In this paper we improves over this state of the broadcast problem in O(log3 n) rounds. Repeatedly art in several ways by presenting a deterministic gossip applying this solution leads to an O(D log3 n) global algorithm that solves the the k-local broadcast problem broadcast in any network with diameter D and thus to in 2(k + log n)log n rounds1. Besides being the first a polylogarithmic time gossip solution for any network efficient deterministic solution to the rumor spreading with polylogarithmic diameter. Using connections to problem this algorithm is interesting in many aspects: spanners one can furthermore get a O(D + logO(1)) It is simpler, more natural, more robust and faster than solution. All these algorithms are inherently randomized in *MIT,haeupler@mit.edu 1Throughout this paper log x denotes dlog2 xe, that is, the both their design and analysis in that they crucially rounded up binary logarithm. rely on the effect that choosing neighbors randomly for 705 Copyright © SIAM. Unauthorized reproduction of this article is prohibited.
