Sublinear Bounds for Randomized Leader Election

VCLA will be hosting a RiSE seminar talk by Peter Robinson on April 18th, 2013.

ABSTRACT

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.