|Abstract of Paper|
Time and Message Optimal Leader Election in Asynchronous Oriented Complete Networks
by Stefan Dobrev
We consider the problem of leader election in asynchronous oriented $N$-node complete networks. We present a leader election algorithm with $O(N)$ message and $O(\log\log N)$ time complexity. The message complexity is optimal and the time complexity is the best under the assumption of message optimality. The best previous leader election algorithm for asynchronous oriented complete networks by Singh  achieves $O(N)$ message and $O(\log N)$ time complexity.