The Complexity of Leader Election
Soumyottam Chatterjee, Gopal Pandurangan, Peter D. Robinson · 2018
Leader election is one of the fundamental problems in distributed computing. In its implicit version, only the leader must know who is the elected leader. This paper focuses on studying the message complexity of leader election in synchronous distributed networks, in particular, in networks of diameter two. Kutten et al. [JACM 2015] showed a fundamental lower bound of Ω(m) (m is the number of edges in the network) on the message complexity of (implicit) leader election that applied also to Monte Carlo randomized algorithms with constant success probability; this lower bound applies for graphs that have diameter at least three. On the other hand, for complete graphs (i.e., diameter 1), Kutten et al. [TCS 2015] established a tight bound of Θ(√n)1 on the message complexity of randomized leader election (n is the number of nodes in the network). For graphs of diameter two, the complexity was not known.