amoebot-model

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.

This paper formally extends the amoebot model of programmable matter to three-dimensional (3D) space using the face-centered cubic lattice. We then give a deterministic distributed algorithm for 2D/3D leader election that elects a leader from among $n$ amoebots in $\mathcal{O}(n)$ rounds in the sequential setting. Finally, we show that our algorithm can be extended to the asynchronous setting, a first for amoebot leader election algorithms.

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.

How can an observed or desired collective behavior be reverse-engineered into local rules that individuals can embody? In this talk, I present a framework for designing stochastic distributed algorithms whose long-run collective behaviors can be formally characterized by phase transitions and can be embodied in analog collectives.

In this dissertation defense, I treat three questions on emergent behavior in programmable matter: What are the minimum individual capabilities necessary to achieve a collective behavior? How can existing algorithms be enhanced to capture realistic assumptions? How can digital algorithms be translated for simple, analog systems?

The world is filled with systems of entities that collaborate in motion, both natural and engineered, that are capable of sophisticated emergent behavior arising from simple interactions of their members. This PhD dissertation collects my work on the amoebot model, stateful and stochastic distributed algorithms for programmable matter, and translations to active granular matter.

We bridge the gap between self-organizing particle systems and tile self-assembly systems by providing a simulation of the amoebot model within the tile automata model.