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

The best previous leader election algorithm for asynchronous oriented
complete networks by Singh [15] achieves $O(N)$ message and $O(\log N)$ time