TY  - JOUR
T1  - Leader election in complete networks.
JF  - SIAM journal on computing.
A1  - Singh, Gurdip
LA  - English
UL  - https://tuklas.up.edu.ph/Record/UP-99796217608823545
AB  - Leader election is a fundamental problem in distributed computing and has a number of applications. This paper studies the problem of leader election in complete asynchronous networks. We present a message-optimal protocol that requires O (N log N) messages and O (N/log N) time, where N is the number of nodes in the system. The time complexity of this protocol is a significant improvement over currently known protocols for this problem. We also give a family of protocols with message and time complexities O (N k) and O (N/k), respectively where log N < k < N. Many problems such as spanning-tree construction and computing a global function are equivalent to leader election in terms of their message and time complexities, and therefore our result improves the time complexity of these problems as well.
KW  - Distributed algorithms.
KW  - Leader election.
KW  - Time complexity.
KW  - Complete networks.
ER  -