Perfect Information Leader Election in log* n+O(1) Rounds

ISSN： 0022-0000

Source： Journal of Computer and System Sciences, Vol.63, Iss.4, 2001-12, pp. : 612-626

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

In the leader election problem, n players wish to elect a random leader. The difficulty is that some coalition of players may conspire to elect one of its own members. We adopt the perfect information model: all communication is by broadcast, and the bad players have unlimited computational power. Protocols proceed in rounds: although players are synchronized between rounds, within each round the bad players may wait to see the inputs of the good players. A protocol is called resilient if a good leader is elected with probability bounded away from 0. We give a simple, constructive leader election protocol that is resilient against coalitions of size βn, for any β<1/2. Our protocol takes log* n+O(1) rounds, each player sending at most log n bits per round. For any constant k, our protocol can be modified to take k rounds and offer resilience against coalitions of size ɛn/(log^(k) n)³, were ɛ is a small enough constant and log^(k) denotes the logarithm iterated k times. This is constructive for k3. The primary component of the above protocols is a new collective sampling protocol: for a set S of large enough (polynomial) size, this protocol generates an element s∈S in a single round so that for any subset T⊂S, Pr[s∈T]|T| |S|^α (1-β) for a constant α>0. © 2001 Elsevier Science (USA).