Sublinear Bounds for Randomized Leader Election

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.

Posted in RiSE Seminar