The Canonical Amoebot Model: Algorithms and Concurrency Control

Abstract

Since the amoebot model of programmable matter was introduced in 2014, it has been extended and modified over ~30 papers to a wide variety of problems. In this talk, I present the canonical amoebot model which unifies the amoebot model’s many assumption variants and addresses the key issue of concurrency. Reimplementing all amoebot communication as message passing allows us to consider traditional adversarial models of concurrency (e.g., synchronous, asynchronous) in addition to the amoebot model’s usual sequential activations where at most one amoebot acts at a time. I then present two complementary approaches to designing concurrent amoebot algorithms: (1) sufficient conditions for concurrent directness embedded directly in an algorithm, and (2) a general framework that uses locks to transform algorithms that are correct in the sequential setting and satisfy certain conventions into algorithms with equivalent behavior in the asynchronous setting.