Distributed Protocols for Leader Election: A Game-Theoretic Perspective

• Published in: ACM transactions on economics and computation 2019-02, Vol.7 (1), p.1-26
• Main Authors: Abraham, Ittai, Dolev, Danny, Halpern, Joseph Y.
• Format: Article
• Language: English
• ISSN: 2167-8375; 2167-8383
• DOI: 10.1145/3303712

We do a game-theoretic analysis of leader election, under the assumption that each agent prefers to have some leader than no leader at all. We show that it is possible to obtain a fair Nash equilibrium, where each agent has an equal probability of being elected leader, in a completely connected network, in a bidirectional ring, and a unidirectional ring, in the synchronous setting. In the asynchronous setting, Nash equilibrium is not quite the right solution concept. Rather, we must consider ex post Nash equilibrium; this means that we have a Nash equilibrium no matter what a scheduling adversary does. We show that ex post Nash equilibrium is attainable in the asynchronous setting in all the networks we consider, using a protocol with bounded running time. However, in the asynchronous setting, we require that n > 2. We show that we can get a fair ex post ϵ-Nash equilibrium if n =2 in the asynchronous setting under some cryptographic assumptions (specifically, the existence of a one-way functions), using a commitment protocol . We then generalize these results to a setting where we can have deviations by a coalition of size k . In this case, we can get what we call a fair k -resilient equilibrium in a completely connected network if n > 2 k ; under the same cryptographic assumptions, we can a get a k -resilient equilibrium in a completely connected network, unidirectional ring, or bidirectional ring if n > k . Finally, we show that under minimal assumptions, not only do our protocols give a Nash equilibrium, they also give a sequential equilibrium, so players even play optimally off the equilibrium path.