CAMERA: CHURN-TOLERANT MUTUAL EXCLUSION FOR THE EDGE

Permalink

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

Title: CAMERA: CHURN-TOLERANT MUTUAL EXCLUSION FOR THE EDGE
Author(s): Khinvasara, Aman
Issue Date: 2023-05-01
Keyword(s): distributed mutual exclusion algorithms, high churn,
Abstract: Mutual exclusion is an essential primitive in distributed systems to ensure at most one process at a time accesses a shared resource. While classical distributed mutual exclusion algorithms assume full, consistent membership, today’s IoT and adhoc networks are characterized by high churn that often leaves membership inconsistent and incomplete. We extend a classical mutual exclusion algorithm by taking advantage of the observation that any two nodes typically have a common friend, even if they don’t know each other. The presented algorithm is tolerant to churn, robust to heterogeneity in membership lists, bandwidth-efficient, and degrades gracefully. We accompany this algorithm with formal proofs of safety, starvation-freedom, and deadlock-freedom; a slow path ensuring safety even when common-case assumptions happen to be false; and experimental results validating performance at scale.
Type of Resource: text
Language: eng

The best of ECE undergraduate research