Fast leader-election protocols with bounded cheaters' edge

We study the leader election problem on n players in the asynchronous full-information model. Our main contention is that the most commonly used performance measure for leader-election protocols, called resilience, is unable to discern whether a small number of players can exercise disproportionate influence on the outcome of a protocol, or not. As a remedy we propose a new quantity, named cheaters' edge, which roughly describes by what multiplicative factor malicious players may increase, through cheating, their probability of getting elected. Arguably, a good protocol must have bounded cheaters' edge.We present polynomial-time constructions of new leader-election protocols that are fast, in terms of the rounds required (5, 5 log n, and log n rounds, respectively), but moreover exhibit bounded cheaters' edge under progressively looser restrictions on the number t of malicious players: t < Θn / log n, t < Θn / √log n log log n, and, eventually, no restriction at all---without relying on any a priori knowledge of t. The latter of these three protocols constitutes the first constructive solution to a problem posed by Alon and Naor more than a decade ago.

Authors

• Spyridon Antonakopoulos

Keywords

• coin-flipping
• distributed computing
• leader election