SCIENCE@home

Quasirandom rumor spreading

Benjamin Doerr,T. Friedrich,Thomas Sauerwald

Published 2008 in ACM-SIAM Symposium on Discrete Algorithms

ABSTRACT

We propose and analyse a quasirandom analogue to the classical push model for disseminating information in networks ("randomized rumor spreading"). In the classical model, in each round each informed node chooses a neighbor at random and informs it. Results of Frieze and Grimmett (Discrete Appl. Math. 1985) show that this simple protocol succeeds in spreading a rumor from one node of a complete graph to all others within <i>O</i><i>(log n)</i> rounds. For the network being a hypercube or a random graph <i>G(n, p)</i> with <i>p</i> ≥ (1 +ε)(log <i>n</i>)/<i>n</i>, also <i>O</i>(log <i>n</i>) rounds suffice (Feige, Peleg. Raghavan, and Upfal, Random Struct. Algorithms 1990). In the quasirandom model, we assume that each node has a (cyclic) list of its neighbors. Once informed, it starts at a random position of the list, but from then on informs its neighbors in the order of the list. Surprisingly, irrespective of the orders of the lists, the above mentioned bounds still hold. In addition, we also show a <i>O</i>(log <i>n</i>) bound for sparsely connected random graphs <i>G(n, p)</i> with <i>p</i> = (log <i>n</i> + <i>f(n))/n</i>, where <i>f(n)</i> → ∞ and <i>f(n)</i> = <i>O</i>(log log <i>n</i>). Here, the classical model needs Θ(log<sup>2</sup>(<i>n</i>)) rounds. Hence the quasirandom model achieves similar or better broadcasting times with a greatly reduced use of random bits.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-60 of 60 references · Page 1 of 1

CITED BY

Showing 1-91 of 91 citing papers · Page 1 of 1