University of Illinois Urbana-Champaign

Churn-tolerant leader election on weakly-consistent membership

Wang, Jiangran

Content Files
WANG-THESIS-2023.pdf

Permalink

https://hdl.handle.net/2142/120286

Description

Title
Churn-tolerant leader election on weakly-consistent membership
Author(s)
Wang, Jiangran
Issue Date
2023-04-19
Director of Research (if dissertation) or Advisor (if thesis)
Gupta, Indranil
Department of Study
Electrical & Computer Eng
Discipline
Electrical & Computer Engr
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
M.S.
Degree Level
Thesis
Keyword(s)
  • leader election
  • membership
  • churn
  • Internet of Things
Abstract
Many distributed systems suffer from churn, such as peer-to-peer file-sharing networks and distributed database systems. Churn in distributed systems is the frequent joining and leaving of nodes, leading to instability and challenges in coordination. Distributed applications running in such systems require underneath them a membership protocol that updates (local) membership lists in spite of churn. On top of this membership layer run coordination protocols including (but not limited to) leader election, mutual exclusion, agreement, etc. In this thesis, we present: i) a membership protocol called Medley-F; ii) a family of leader election protocols that are churn-tolerant; and iii) two protocols that estimate churn in distributed systems. First, we present Medley-F, a weakly-consistent membership protocol for IoT networks. It is an enhanced version of an existing system (Medley), and Medley-F utilizes active and passive strategies to reduce failure detection tail latency. We show both simulation results, as well as deployment results, atop Raspberry Pi devices. Second, 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 num- ber of nodes necessary to achieve safety; ii) use optimism so that decisions are made faster when churn is low; iii) incorporate a preference for elect- ing healthier nodes as leaders. We present experimental results from both a trace-driven simulation and our implementation atop Raspberry Pi devices, including a comparison against Zookeeper. Third, we present two protocols to dynamically estimate churn with the underlying membership changes continuously. The key ideas are to: i) sample memberships from a small subset of nodes; ii) utilize intermediate results during leader election. We show simulation results of the estimation accuracy of both protocols and the effect of underestimating churn on leader election safety.
Graduation Semester
2023-05
Type of Resource
Thesis
Handle URL
https://hdl.handle.net/2142/120286
Copyright and License Information
Copyright 2023 Jiangran Wang

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois