TIME AND MESSAGE BOUNDS FOR ELECTION IN SYNCHRONOUS AND ASYNCHRONOUS COMPLETE NETWORKS

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.