Leader election in complete networks

Gurdip Singh

Leader election in complete networks

Gurdip Singh

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

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
Editors	Anon
Publisher	Publ by ACM
Pages	179-190
Number of pages	12
ISBN (Print)	0897914953
State	Published - Dec 1 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

Cite this

@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",

month = dec,

day = "1",

language = "English (US)",

isbn = "0897914953",

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

publisher = "Publ by ACM",

pages = "179--190",

editor = "Anon",

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/12/1

Y1 - 1992/12/1

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

M3 - Conference contribution

AN - SCOPUS:0026992716

SN - 0897914953

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

A2 - Anon, null

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

Other files and links

Cite this