Abstract (Lisa Higham)
Several tasks in distributed computing require one processor, a
leader, to be distinguished from among several anonymous
processors.
This can be achieved by using random walks as follows.
Initially, each processor contending for leadership gets a
token.
A processor that has a token passes it randomly to one of its
neighbors.
When more than one token meet at one processor, they merge to
one token.
In a connected undirected graph, eventually all tokens will merge to
one token.
The expected time until several random walks on a graph collapse
into one characterizes the performance of this protocol.
In this talk, we will derive a new technique for proving bounds on the
expected time until an arbitrary number of random walks meet, and
apply this technique to prove a bound that is stronger and more general
than a bound first suggested by Tetali and Winkler.
We will also see that the stronger bound yields tight results for
for rings of processors.
This is joint work with graduate student Jolanta Warpechowska-Gruca
and Professor Bshouty.
Last modified: May 17, 1995.
Kim Skak Larsen
(kslarsen@imada.sdu.dk)