TY - GEN

T1 - Efficient distributed algorithms for leader election in complete networks

AU - Singh, Gurdip

PY - 1991/5/1

Y1 - 1991/5/1

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 -