Camera: Churn-Tolerant Mutual Exclusion for the Edge

Khinvasara, Aman; Gupta, Indranil

Permalink

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

Description

Title

Camera: Churn-Tolerant Mutual Exclusion for the Edge

Author(s)

• Khinvasara, Aman
• Gupta, Indranil

Issue Date

2024

Keyword(s)

• edge
• parallel computing

Abstract

Emerging edge and IoT networks are characterized by churn, wherein nodes join, leave, and fail continuously. Together with flaky network links and delays in edge and IoT systems, this means nodes have differing views of the system membership at any point of time. This paper focuses on the classical mutual exclusion problem---which ensures at most one node executes the ``critical section'' at any point in time---over such churned edge networks. We first show that two classical algorithms for mutual exclusion (Ricart-Agrawala and Maekawa) violate safety even under very small amounts of churn (up to 4 churned entries in membership lists). We then present Camera, a churn-tolerant variant of Ricart-Agrawala's algorithm. We formally prove Camera satisfies key properties including safety, deadlock-freedom, and starvation-freedom. Our trace-driven simulation results, using synthetic traces, distributions, and churn traces from peer to peer environments, show that Camera has scalable wait times and bandwidth overheads.

Type of Resource

text

Owning Collections