Efficient distributed algorithms for leader election in complete networks

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

15 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings - International Conference on Distributed Computing Systems
Editors Anon
PublisherIEEE Computer Society
Pages472-479
Number of pages8
ISBN (Print)0818621443
StatePublished - May 1 1991
Externally publishedYes
EventProceedings of the 11th International Conference on Distributed Computing Systems - Arlington, TX, USA
Duration: May 20 1991May 24 1991

Publication series

NameProceedings - International Conference on Distributed Computing Systems

Other

OtherProceedings of the 11th International Conference on Distributed Computing Systems
CityArlington, TX, USA
Period5/20/915/24/91

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Efficient distributed algorithms for leader election in complete networks'. Together they form a unique fingerprint.

  • Cite this

    Singh, G. (1991). Efficient distributed algorithms for leader election in complete networks. In Anon (Ed.), Proceedings - International Conference on Distributed Computing Systems (pp. 472-479). (Proceedings - International Conference on Distributed Computing Systems). IEEE Computer Society.