Efficient distributed algorithms for leader election in complete networks

An efficient protocol for leader election in an asynchronous complete network is presented. The time complexity of the protocol is better than the currently known protocols for this problem. A message optimal protocol is presented that requires O(N/log N) time, where N is the number of nodes in the network. Also given is family of protocols with message and time complexities O(Nk) and O(N/k) respectively, where log N⩽k⩽N. Many problems such as spanning tree construction, computing a global function, etc., are equivalent to leader election in terms of their message and time complexities, and therefore the author´s results also improve the time complexity of these problems