Scalable leader election
Valerie Jean King, Jared Saia, Vishal Sanwalani, Erik Vee · Symposium on Discrete Algorithms · 2006
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