We study gossip algorithms for the rumor spreading problem which asks one node to deliver a rumor to all nodes in an unknown network. We present the first protocol for any expander graph @math with @math nodes such that, the protocol informs every node in @math rounds with high probability, and uses @math random bits in total. The runtime of our protocol is tight, and the randomness requirement of @math random bits almost matches the lower bound of @math random bits for dense graphs. We further show that, for many graph families, polylogarithmic number of random bits in total suffice to spread the rumor in @math rounds. These results together give us an almost complete understanding of the randomness requirement of this fundamental gossip process. Our analysis relies on unexpectedly tight connections among gossip processes, Markov chains, and branching programs. First, we establish a connection between rumor spreading processes and Markov chains, which is used to approximate the rumor spreading time by the mixing time of Markov chains. Second, we show a reduction from rumor spreading processes to branching programs, and this reduction provides a general framework to derandomize gossip processes. In addition to designing rumor spreading protocols, these novel techniques may have applications in studying parallel and multiple random walks, and randomness complexity of distributed algorithms.
The study of determining and reducing the amount of randomness required for rumor spreading has been studied extensively in the past years. proposed a version of the rumor spreading push protocol. In contrast to @math random bits that used in the standard push model, the quasi-random rumor spreading model uses @math random bits, and has been shown to be efficient on several graph topologies @cite_4 @cite_29 . Further progress along this line include @cite_21 @cite_30 . Besides this, researchers also studied the question of designing randomness-efficient or deterministic protocols for similar problems. For instance, presented one deterministic gossip algorithm for the @math -local broadcast and the global broadcast problem. However, the algorithms in @cite_11 require that all nodes in the graph have unique identifiers (UID), and every node knows its own and the neighbors' UIDs. Hence the techniques developed there cannot be applied to our setting.
@cite_30 @cite_4 @cite_29 @cite_21 @cite_11
2148754694 2078958987 1771950282 2009267577 2952550120
We consider the classical rumor spreading problem, where a piece of information must be disseminated from a single node to all n nodes of a given network. We devise two simple push-based protocols, in which nodes choose the neighbor they send the information to in each round using pairwise independent hash functions, or a pseudo-random generator, respectively. For several wellstudied topologies our algorithms use exponentially fewer random bits than previous protocols. For example, in complete graphs, expanders, and random graphs only a polylogarithmic number of random bits are needed in total to spread the rumor inO(logn) rounds with high probability. Previous explicit algorithms, e.g., [10, 17, 6, 15], require ( n) random bits to achieve the same round complexity. For complete graphs, the amount of randomness used by our hashing-based algorithm is within anO(logn)-factor of the theoretical minimum determined by Giakkoupis and Woelfel [15]. In this paper, we provide a detailed comparison between a fully randomized protocol for rumor spreading on a complete graph and a quasirandom protocol introduced by Doerr, Friedrich, and Sauerwald [Quasirandom rumor spreading, in Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, SIAM, Philadelphia, 2008, pp. 773-781]. In the former, initially there is one vertex which holds a piece of information, and during each round every one of the informed vertices chooses uniformly at random and independently one of its neighbors and informs it. In the quasirandom version of this method (cf. Doerr, Friedrich, and Sauerwald) each vertex has a cyclic list of its neighbors. Once a vertex has been informed, it chooses uniformly at random only one neighbor. In the following round, it informs this neighbor, and at each subsequent round it picks the next neighbor from its list and informs it. We give a precise analysis of the evolution of the quasirandom protocol on the complete graph with @math vertices and show that it evolves essentially in the same way as the randomized protocol. In particular, if @math denotes the number of rounds that are needed until all vertices are informed, we show that for any slowly growing function @math , we have @math , with probability @math . Randomized rumor spreading is an efficient protocol to distribute information in networks. Recently, a quasirandom version has been proposed and proven to work equally well on many graphs and better for sparse random graphs. In this work we show three main results for the quasirandom rumor spreading model. We exhibit a natural expansion property for networks which suffices to make quasirandom rumor spreading inform all nodes of the network in logarithmic time with high probability. This expansion property is satisfied, among others, by many expander graphs, random regular graphs, and Erdős-Renyi random graphs. For all network topologies, we show that if one of the push or pull model works well, so does the other. We also show that quasirandom rumor spreading is robust against transmission failures. If each message sent out gets lost with probability f , then the runtime increases only by a factor of @math . We investigate the randomness requirements of the classical rumor spreading problem on fully connected graphs with n vertices. In the standard random protocol, where each node that knows the rumor sends it to a randomly chosen neighbor in every round, each node needs O((log n)2) random bits in order to spread the rumor in O(log n) rounds with high probability (w.h.p.). For the simple quasirandom rumor spreading protocol proposed by Doerr, Friedrich, and Sauerwald (2008), [log n] random bits per node are sufficient. A lower bound by Doerr and Fouz (2009) shows that this is asymptotically tight for a slightly more general class of protocols, the so-called gate-model. In this paper, we consider general rumor spreading protocols. We provide a simple push-protocol that requires only a total of O(n log log n) random bits (i.e., on average O(log log n) bits per node) in order to spread the rumor in O(log n) rounds w.h.p. We also investigate the theoretical minimal randomness requirements of efficient rumor spreading. We prove the existence of a (non-uniform) push-protocol for which a total of 2 log n + log log n + o(log log n) random bits suffice to spread the rumor in log n + ln n + O(1) rounds with probability 1 − o(1). This is contrasted by a simple time-randomness tradeoff for the class of all rumor spreading protocols, according to which any protocol that uses log n − log log n − ω(1) random bits requires ω(log n) rounds to spread the rumor. 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. Recently, non-uniform random gossip schemes were devised to allow efficient rumor spreading in networks with bottlenecks. In particular, [Censor-, STOC'12] gave an O(log^3 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. This and all prior gossip algorithms for the rumor spreading problem have been inherently randomized in their design and analysis. This resulted in a parallel research direction trying 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. The general intuition and consensus of these results has been that randomization plays a important role in effectively spreading rumors. In this paper we improves over this state of the art in several ways by presenting a deterministic gossip algorithm that solves the the k-local broadcast problem in 2(k+log n)log 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.