dynamic-networks

Reimagining graph-based models for moving and interacting entities. Designing concurrent and distributed algorithms that are robust to highly dynamic environments. Coordinating anonymous entities across time-varying tasks.

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.