Leader election in complete networks

Gurdip Singh

doi:10.1145/135419.135457

Leader election in complete networks

Gurdip Singh

Research output: Chapter in Book/Entry/Poem › Conference contribution

15 Scopus citations

Abstract

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.

Original language	English (US)
Title of host publication	Proceedings of the Annual ACM Symposium on Principles of Distributed Computing
Publisher	Publ by ACM
Pages	179-190
Number of pages	12
ISBN (Print)	0897914953, 9780897914956
DOIs	https://doi.org/10.1145/135419.135457
State	Published - 1992
Externally published	Yes
Event	Proceedings of the 11th Annual ACM Symposium on Principles of Distributed Computing - Vancouver, BC, Can Duration: Aug 10 1992 → Aug 12 1992

Publication series

Name	Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

Other

Other	Proceedings of the 11th Annual ACM Symposium on Principles of Distributed Computing
City	Vancouver, BC, Can
Period	8/10/92 → 8/12/92

ASJC Scopus subject areas

Software
Hardware and Architecture
Computer Networks and Communications

Access to Document

10.1145/135419.135457

Cite this

Singh, G 1992, Leader election in complete networks. in Proceedings of the Annual ACM Symposium on Principles of Distributed Computing. Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, Publ by ACM, pp. 179-190, Proceedings of the 11th Annual ACM Symposium on Principles of Distributed Computing, Vancouver, BC, Can, 8/10/92. https://doi.org/10.1145/135419.135457

@inproceedings{a87868e7132e4259b34f4d244d930566,

title = "Leader election in complete networks",

abstract = "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.",

author = "Gurdip Singh",

year = "1992",

doi = "10.1145/135419.135457",

language = "English (US)",

isbn = "0897914953",

series = "Proceedings of the Annual ACM Symposium on Principles of Distributed Computing",

publisher = "Publ by ACM",

pages = "179--190",

booktitle = "Proceedings of the Annual ACM Symposium on Principles of Distributed Computing",

note = "Proceedings of the 11th Annual ACM Symposium on Principles of Distributed Computing ; Conference date: 10-08-1992 Through 12-08-1992",

}

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 -

Leader election in complete networks

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this