One frequently studied problem in the context of information dissemination in communication networks is the broadcasting problem.
In this paper, we study the following randomized broadcasting protocol: At some time
t an information
r is placed at one of the nodes of a graph
G. In the succeeding steps, each informed node chooses one neighbor, independently and uniformly at random, and informs this
neighbor by sending a copy of
r to it.
First, we consider the relationship between randomized broadcasting and random walks on graphs. In particular, we prove that
the runtime of the algorithm described above is upper bounded by the corresponding mixing time, up to a logarithmic factor.
One key ingredient of our proofs is the analysis of a continuous-type version of the afore mentioned algorithm, which might
be of independent interest. Then, we introduce a general class of Cayley graphs, including (among others) Star graphs, Transposition
graphs, and Pancake graphs. We show that randomized broadcasting has optimal runtime on all graphs belonging to this class.
Finally, we develop a new proof technique by combining martingale tail estimates with combinatorial methods. Using this approach,
we show the optimality of our algorithm on another Cayley graph and obtain new knowledge about the runtime distribution on
several Cayley graphs.
This work was partially supported by German Science Foundation (DFG) Research Training Group GK-693 of the Paderborn Institute
for Scientific Computation (PaSCo) and by the EU within the 6th Framework Programme under contract 001907 “Dynamically Evolving,
Large Scale Information Systems” (DELIS).