Leader election in complete networks

Gurdip Singh

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


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
Issue number3
StatePublished - Jun 1997
Externally publishedYes


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

ASJC Scopus subject areas

  • General Computer Science
  • General Mathematics


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

Cite this