Quasirandom Rumor Spreading
Abstract: In the classical randomized rumor spreading model, we start with
one node of a graph knowing a ``rumor''. Then in each round each node that
knows the rumor chooses a neighbor at random and informs it of the rumor.
Results of Frieze and Grimmett 1985 show that in a complete graph on n
vertices, this simple protocol succeeds in spreading the rumor from one node
to all others within (log_2(n) + ln(n))(1 + o(1)) rounds. For the network
being a hypercube or a random graph G(n,p) with p <= (1 + epsilon)(log n)/n,
again O(log n) rounds suffice, see Feige, Peleg, Raghavan, and Upfal 1990.
We propose and analyse a quasirandom analogue of the randomized rumor
spreading problem described above. 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 an O(log
n) bound for sparsely connected random graphs G(n,p) with p=(log n +
f(n))/n, where f(n) goes to infinity and f(n)=O(log log n). Here, the
classical model needs Theta(log^2(n)) rounds.