Churn-tolerant leader election on weakly-consistent membership

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.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Electrical & Computer Engr

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2023

Author dc:creator

• Wang, Jiangran

Contributors dc:contributor

• Gupta, Indranil

• Leader Election
• Membership
• Churn
• Internet Of Things

Statement dc:rights

• Copyright 2023 Jiangran Wang

Language dc:language

en, eng

Handle dc:identifier

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

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F120286