Abstract Scalable Leader Election

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. We assume a point-to-point full information model. This is similar to the full information model, but harder in the sense that in a given round, a bad processor may send different messages to different processors, rather than having to broadcast the same message to every processor. To the best of our knowledge, we present the first leader election protocol that 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.