Time and Message Bounds for Election in Synchronous and Asynchronous Complete Networks

Abstract

This paper addresses the problem of distributively electing a leader in both synchronous and asynchronous complete networks. $O(n\log n)$ messages synchronous and asynchronous algorithms are presented. The time complexity of the synchronous algorithm is $O(\log n)$, while that of the asynchronous algorithm is $O(n)$. In the synchronous case, a lower bound of $\Omega (n\log n)$ on the message complexity is proven. It is also proven that any message-optimal synchronous algorithm requires $\Omega (\log n)$ time. In proving these bounds, the type of operations performed by nodes are not restricted. The bounds thus apply to general algorithms and not just to comparison-based algorithms.