Leader election in complete networks

Research output: Contribution to journalArticle

10 Scopus citations

Abstract

Leader election is a fundamental problem in distributed computing and has a number of applications. This paper studies the problem of leader election in complete asynchronous networks. We present a message-optimal protocol that requires O(N log N) messages and O(N/ log N) time, where N is the number of nodes in the system. The time complexity of this protocol is a significant improvement over currently known protocols for this problem. We also give a 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 and computing a global function are equivalent to leader election in terms of their message and time complexities, and therefore our result improves the time complexity of these problems as well.

Original languageEnglish (US)
Pages (from-to)772-785
Number of pages14
JournalSIAM Journal on Computing
Volume26
Issue number3
DOIs
StatePublished - Jun 1997
Externally publishedYes

Keywords

  • Complete networks
  • Distributed algorithms
  • Leader election
  • Time complexity

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Leader election in complete networks'. Together they form a unique fingerprint.

  • Cite this