\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Spyros Angelopoulos, Benjamin Doerr, Anna Huber and Konstantinos Panagiotou}
%
%
\medskip
\noindent
%
%
{\bf Tight Bounds for Quasirandom Rumor Spreading}
%
%
\vskip 5mm
\noindent
%
%
%
%
This paper addresses the following fundamental problem: Suppose that
in a group of $n$ people, where each person knows all other group
members, a single person holds a piece of information that must be
disseminated to everybody within the group.  How should the people
propagate the information so that after short time everyone is
informed?

The classical approach, known as the {\em push model}, requires that
in each round, every informed person selects some other person in the
group at random, whom it then informs.  In a different model, known as
the \emph{quasirandom push model}, each person maintains a cyclic
list, i.e., permutation, of all members in the group (for instance, a
contact list of persons).  Once a person is informed, it chooses a
random member in its own list, and from that point onwards, it informs
a new person per round, in the order dictated by the list.

In this paper we show that with probability $1-o(1)$ the quasirandom
protocol informs everybody in $(1 \pm o(1))\log_2 n+\ln n$ rounds;
furthermore we also show that this bound is tight. This result,
together with previous work on the randomized push model, demonstrates
that irrespectively of the choice of lists, quasirandom broadcasting
is as fast as broadcasting in the randomized push model, up to lower
order terms. At the same time it reduces the number of random bits
from $O(\log^2 n)$ to only $\lceil\log_2 n\rceil$ per person.


\bye