**Date: **
Thursday, April 18, 2013

**Venue: **TU Wien

In this talk we look at randomized leader election in synchronous distributed

networks. We first present a distributed leader election algorithm for complete

n-node networks that runs in O(1) rounds and (with high probability) takes only

O(\sqrt{n} \log^{3/2}(n)) messages to elect a unique leader (with high

probability). We extend this algorithm to solve leader election on any

connected non-bipartite n-node network G in O(\tau(G)) time and

O(\tau(G) \sqrt{n} \log^{3/2}(n)) messages, where \tau(G) is the mixing time of

a random walk on G. The above result implies highly efficient (sublinear

running time and messages) leader election algorithms for arbitrary networks

with small mixing times, such as expander graphs and hypercubes. In contrast,

previous leader election algorithms had at least linear message complexity in

complete graphs and even super-linear message complexity when considering

time-efficient algorithms.

Finally, we show a lower bound of \Omega(\sqrt{n}) messages for any leader

election algorithm that succeeds with probability at least 1/e + \epsilon, for

any arbitrarily small constant \epsilon > 0.

This talk is based on joint work with Shay Kutten, Gopal Pandurangan,

David Peleg, and Amitabh Trehan.