Abstract of Paper

Time and Message Optimal Leader Election in Asynchronous Oriented Complete Networks
by Stefan Dobrev

Abstract:

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 [15] achieves $O(N)$ message and $O(\log N)$ time
complexity.