Local Mutual Exclusion for Dynamic, Anonymous, Bounded Memory Message Passing Systems

Abstract

Traditionally, distributed computing models communication either as message passing or shared memory. But recent work applying distributed computing techniques to swarm robotics, programmable matter, mobile sensor networks, and biological systems instead focus on more abstract interactions. In this talk, we discuss how to bridge these paradigms, especially in the concurrent, dynamic setting where agents (nodes) act simultaneously and connections between them change over time. In particular, we introduce the local mutual exclusion problem which tasks nodes with acquiring locks over themselves and their “persistent neighbors” who remain connected to them over the course of the locking attempt. We give a randomized distributed algorithm for this problem satisfying mutual exclusion (non-intersecting lock sets) and lockout freedom (eventual success with probability 1) under both semi-synchronous and asynchronous concurrency. Moreover, we achieve this with only $\mathcal{O}(\Delta)$ memory per node and messages of size $\Theta(1)$, where $\Delta$ is the maximum number of connections per node. We conclude by discussing applications of our algorithm to population protocols and the canonical amoebot model of programmable matter.