Fair Leader Election for Rational Agents in Asynchronous Rings and Networks

We study a game theoretic model where a coalition of processors might collude to bias the outcome of the protocol, where we assume that the processors always prefer any legitimate outcome over a non-legitimate one. We show that the problems of Fair Leader Election and Fair Coin Toss are equivalent, and focus on Fair Leader Election. Our main focus is on a directed asynchronous ring of n processors, where we investigate the protocol proposed by Abraham et al. [4] and studied in Afek et al. [5]. We show that in general the protocol is resilient only to sub-linear size coalitions. Specifically, we show that O( p n logn) randomly located processors or O( 3 n) adversarially located processors can force any outcome. We complement this by showing that the protocol is resilient to any adversarial coalition of size O( 4 n). We propose a modification to the protocol, and show that it is resilient to every coalition of size ?( n), by exhibiting both an attack and a resilience result. For every k 1, we define a family of graphs Gk that can be simulated by trees where each node in the tree simulates at most k processors. We show that for every graph in Gk , there is no fair leader election protocol that is resilient to coalitions of size k. Our result generalizes a previous result of Abraham et al. [4] that states that for every graph, there is no fair leader election protocol which is resilient to coalitions of size ?n/2 ?.