Scalable Leader Election
by Valerie King and Erik Vee

Abstract

In the leader election problem, there are n processors of which (1- b) n are good. The problem is to design a distributed protocol to elect a good leader from the set of all processors. In this paper, we present a scalable leader election protocol. Our protocol is scalable in the sense that each good processor sends and processes a number of bits which is only polylogarithmic in n. (We assume no limit on the number of messages sent by bad processors.) For b<1/3, our protocol elects a good leader with constant probability and ensures that a 1-o(1) fraction of the good processors know this leader.

To the best of our knowledge, we present the first leader election protocol which ensures that each good processor sends and processes a sublinear number of bits. Having reduced the problem of leader election to one of informing all good processors of a bit held by 1-o(1) fraction of good processors, we conjecture that the solution to this problem is not possible within polylogarithmic message bounds.

Our techniques can be used to provide scalable solutions to Byzantine agreement and other problems.