Churn-Tolerant Leader Election Protocols

Jiangran Wang, Indranil Gupta

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


Classical leader election protocols typically assume complete and correct knowledge of underlying membership lists at all participating nodes. Yet many edge and IoT settings are dynamic, with nodes joining, leaving, and failing continuously―a phenomenon called churn. This implies that in any membership protocol, a given node's membership list may have entries that are missing (e.g., false positive detections, or newly joined nodes whose information has not spread yet) or stale (e.g., failed nodes that are undetected)―these would render classical election protocols incorrect. We present a family of four leader election protocols that are churn-tolerant (or c-tolerant). The key ideas are to: i) involve the minimum number of nodes necessary to achieve safety; ii) use optimism so that decisions are made faster when churn is low; iii) incorporate a preference for electing healthier nodes as leaders. We prove the correctness and safety of our c-tolerant protocols and show their message complexity is optimal. We present experimental results from both a trace-driven simulation as well as our implementation atop Raspberry Pi devices, including a comparison against Zookeeper.

Original languageEnglish (US)
Title of host publicationProceedings - 2023 IEEE 43rd International Conference on Distributed Computing Systems, ICDCS 2023
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages12
ISBN (Electronic)9798350339864
StatePublished - 2023
Externally publishedYes
Event43rd IEEE International Conference on Distributed Computing Systems, ICDCS 2023 - Hong Kong, China
Duration: Jul 18 2023Jul 21 2023

Publication series

NameProceedings - International Conference on Distributed Computing Systems


Conference43rd IEEE International Conference on Distributed Computing Systems, ICDCS 2023
CityHong Kong


  • Churn
  • Edge Computing
  • Leader Election
  • Membership

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'Churn-Tolerant Leader Election Protocols'. Together they form a unique fingerprint.

Cite this