Perfect Information Leader Election in log* n+O(1) Rounds
✍ Scribed by Alexander Russell; David Zuckerman
- Book ID
- 102587301
- Publisher
- Elsevier Science
- Year
- 2001
- Tongue
- English
- Weight
- 168 KB
- Volume
- 63
- Category
- Article
- ISSN
- 0022-0000
No coin nor oath required. For personal study only.
✦ Synopsis
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 bn, for any b < 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 en/(log (k) n) 3 , were e 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| a (1 -b) for a constant a > 0.