mutual-exclusion

We study the local mutual exclusion problem for weakly capable nodes whose connections change over time. This problem tasks each node with acquiring locks for itself and its “persistent neighbors” that remain connected to it during the lock request. Our algorithm solves this problem using only bounded memory and messages and can be applied to population protocols and the canonical amoebot model.

This talk presents a randomized distributed algorithm for local mutual exclusion, a new variant of mutual exclusion tasking nodes to acquire locks over themselves and their “persistent neighbors” even as their connections change over time. I then discuss its applications to populations protocols and the canonical amoebot model.