DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE ODENSE UNIVERSITY Meeting Times of Random Walks on Graphs Lisa Higham Department of Computer Science University of Calgary Tuesday, June 6, 1995, at 2:15 PM The Seminar Room 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. Teresa M. Przytycka