On the complexities of leader election algorithms

We show the relationship between the number of messages and time for leader election in general networks. Specifically, the paper proves that every O(D)¹ time algorithm for leader election in general networks requires Ω(m log D) messages. We show that this lower bound is tight by presenting a simple O(m log D) message complexity and O(D) time distributed algorithm for leader election in general networks. Finally, B. Awerbuch (1987) presented an O(m+n log n) message and O(n) time distributed algorithm for leader election in general networks, which is optimal for the number of messages. We present another algorithm that matches Awerbuch´s complexities, but our algorithm is simpler than Awerbuch´s algorithm