hide
Free keywords:
-
Abstract:
In this paper, we provide a detailed comparison between a fully randomized
protocol for rumour spreading on a complete graph
and a quasirandom protocol introduced by Doerr, Friedrich and Sauerwald (2008).
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 one of its neighbours uniformly at random
and independently and informs it. In the quasirandom version of this method
(cf. Doerr et al.) each vertex has a cyclic list of
its neighbours. Once a vertex has been informed, it chooses uniformly at random
only one neighbour. In the following round, it informs this neighbour and at
each subsequent round it picks the next neighbour from its list and informs it.
We give a precise analysis of the evolution of the quasirandom protocol on the
complete graph with $n$ vertices
and show that it evolves essentially in the same way as the randomized
protocol.
In particular, if $S(n)$ denotes the number of rounds that are needed until all
vertices are informed, we show that for any
slowly growing function $\omega (n)$
$$\log_2 n + \ln n - 4\ln \ln n \leq S(n) \leq \log_2 n + \ln n + \omega (n),$$
with probability $1-o(1)$.
