Leader election in complete networks

Research output: Chapter in Book/Report/Conference proceedingConference contribution

13 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 languageEnglish (US)
Title of host publicationProceedings of the Annual ACM Symposium on Principles of Distributed Computing
Editors Anon
PublisherPubl by ACM
Pages179-190
Number of pages12
ISBN (Print)0897914953
StatePublished - Dec 1 1992
Externally publishedYes
EventProceedings of the 11th Annual ACM Symposium on Principles of Distributed Computing - Vancouver, BC, Can
Duration: Aug 10 1992Aug 12 1992

Publication series

NameProceedings of the Annual ACM Symposium on Principles of Distributed Computing

Other

OtherProceedings of the 11th Annual ACM Symposium on Principles of Distributed Computing
CityVancouver, BC, Can
Period8/10/928/12/92

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this

Singh, G. (1992). Leader election in complete networks. In Anon (Ed.), Proceedings of the Annual ACM Symposium on Principles of Distributed Computing (pp. 179-190). (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing). Publ by ACM.