TY - GEN

T1 - Leader election in complete networks

AU - Singh, Gurdip

PY - 1992

Y1 - 1992

N2 - This paper presents protocols for leader election in complete networks. The protocols are message optimal and their time complexities are a significant improvement over currently known protocols for this problem. For asynchronous complete networks with sense of direction, we propose a protocol which requires O(N) messages and O(logN) time. For asynchronous complete network without sense of direction, we show that Ω(N/logN) is a lower bound on the time complexity of any message optimal election protocol and we present a family of protocols which requires O(Nk) messages and O(N/k) time, logN≤k≤N. Our results also improve the time complexity of several other related problems such as spanning tree construction, computing a global function, etc.

AB - This paper presents protocols for leader election in complete networks. The protocols are message optimal and their time complexities are a significant improvement over currently known protocols for this problem. For asynchronous complete networks with sense of direction, we propose a protocol which requires O(N) messages and O(logN) time. For asynchronous complete network without sense of direction, we show that Ω(N/logN) is a lower bound on the time complexity of any message optimal election protocol and we present a family of protocols which requires O(Nk) messages and O(N/k) time, logN≤k≤N. Our results also improve the time complexity of several other related problems such as spanning tree construction, computing a global function, etc.

UR - http://www.scopus.com/inward/record.url?scp=0026992716&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0026992716&partnerID=8YFLogxK

U2 - 10.1145/135419.135457

DO - 10.1145/135419.135457

M3 - Conference contribution

AN - SCOPUS:0026992716

SN - 0897914953

SN - 9780897914956

T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

SP - 179

EP - 190

BT - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

PB - Publ by ACM

T2 - Proceedings of the 11th Annual ACM Symposium on Principles of Distributed Computing

Y2 - 10 August 1992 through 12 August 1992

ER -