TY - GEN
T1 - Efficient distributed algorithms for leader election in complete networks
AU - Singh, Gurdip
PY - 1991/5
Y1 - 1991/5
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0026158770&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0026158770&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:0026158770
SN - 0818621443
T3 - Proceedings - International Conference on Distributed Computing Systems
SP - 472
EP - 479
BT - Proceedings - International Conference on Distributed Computing Systems
A2 - Anon, null
PB - IEEE Computer Society
T2 - Proceedings of the 11th International Conference on Distributed Computing Systems
Y2 - 20 May 1991 through 24 May 1991
ER -