Churn-tolerant leader election on weakly-consistent membership

Wang, Jiangran

Permalink

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

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

Copyright and License Information

Copyright 2023 Jiangran Wang

Owning Collections