On the complexities of leader election algorithms
Hosame H. Abu-Amara, Arkady Kanevsky · 2002
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)/sup 1/ time algorithm for leader election in general networks requires /spl Omega/(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.>