distributed-algorithms

Self-Organizing Particle Systems (SOPS)
Abstracting programmable matter using the (canonical) amoebot model. Developing distributed algorithms for tasks of self-organization. Rigorously analyzing these behaviors for provable guarantees on correctness, runtime, and reliability.
GitHub SOPSLab@ASU
Self-Organizing Particle Systems (SOPS)
The Canonical Amoebot Model: Algorithms and Concurrency Control
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.
Cite Project DOI arXiv Conference Version
The Canonical Amoebot Model: Algorithms and Concurrency Control
Adaptive Self-Organization in Anonymous 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.
SAND Conference
Adaptive Self-Organization in Anonymous Dynamic Networks
Local Mutual Exclusion for Dynamic, Anonymous, Bounded Memory Message Passing Systems
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.
Cite Project DOI arXiv Talk
Local Mutual Exclusion for Dynamic, Anonymous, Bounded Memory Message Passing Systems
Local Mutual Exclusion for Dynamic, Anonymous, Bounded Memory Message Passing Systems
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.
March 29, 2022 5:20 PM SAND 2022
Project Slides Paper
Local Mutual Exclusion for Dynamic, Anonymous, Bounded Memory Message Passing Systems
The Canonical Amoebot Model: Algorithms and Concurrency Control
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.
October 5, 2021 6:20 PM DISC 2021
Project Slides Video Paper
The Canonical Amoebot Model: Algorithms and Concurrency Control
The Canonical Amoebot Model: Algorithms and Concurrency Control
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.
Cite Project DOI arXiv Talk Journal Version
The Canonical Amoebot Model: Algorithms and Concurrency Control
Algorithmic Foundations of Emergent Behavior in Analog Collectives
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.
July 14, 2021 12:15 PM SFI Seminar
Project Project Slides Video
Algorithmic Foundations of Emergent Behavior in Analog Collectives
A Distributed, Stochastic Framework for Active Matter
Harnessing phase changes from statistical physics in algorithm design. Incorporating algorithmic theory in robot design and manufacturing. Making analogies between macro-scale robot swarm dynamics and the physics of granular active matter systems.
SOPSLab@ASU CRABLab@GaTech
A Distributed, Stochastic Framework for Active Matter
Collaborating in Motion: Distributed and Stochastic Algorithms for Emergent Behavior in Programmable Matter
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?
March 15, 2021 9:00 AM PhD Dissertation Defense
Project Project Slides Video Dissertation
Collaborating in Motion: Distributed and Stochastic Algorithms for Emergent Behavior in Programmable Matter