concurrency

We present the canonical amoebot model, an updated formalization of the amoebot model of programmable matter that standardizes a hierarchy of assumption variants and addresses concurrency. We then demonstrate two approaches to concurrent algorithm design: embedding concurrency control directly, and leveraging a novel concurrency control framework.

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.

This talk introduces the canonical amoebot model of programmable matter, a revision of the amoebot model that standardizes a hierarchy of assumption variants and treats all amoebot communication as message passing to facilitate studies of concurrency. I then present two complementary approaches to designing concurrent amoebot algorithms.

We present the canonical amoebot model, an updated formalization of the amoebot model of programmable matter that standardizes a hierarchy of assumption variants and addresses concurrency. We then demonstrate two approaches to concurrent algorithm design: embedding concurrency control directly, and leveraging a novel concurrency control framework.