License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2021.20
URN: urn:nbn:de:0030-drops-148227
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14822/
Daymude, Joshua J. ;
Richa, Andréa W. ;
Scheideler, Christian
The Canonical Amoebot Model: Algorithms and Concurrency Control
Abstract
The amoebot model abstracts active programmable matter as a collection of simple computational elements called amoebots that interact locally to collectively achieve tasks of coordination and movement. Since its introduction (SPAA 2014), a growing body of literature has adapted its assumptions for a variety of problems; however, without a standardized hierarchy of assumptions, precise systematic comparison of results under the amoebot model is difficult. We propose the canonical amoebot model, an updated formalization that distinguishes between core model features and families of assumption variants. A key improvement addressed by the canonical amoebot model is concurrency. Much of the existing literature implicitly assumes amoebot actions are isolated and reliable, reducing analysis to the sequential setting where at most one amoebot is active at a time. However, real programmable matter systems are concurrent. The canonical amoebot model formalizes all amoebot communication as message passing, leveraging adversarial activation models of concurrent executions. Under this granular treatment of time, we take two complementary approaches to concurrent algorithm design. Using hexagon formation as a case study, we first establish a set of sufficient conditions for algorithm correctness under any concurrent execution, embedding concurrency control directly in algorithm design. We then present a concurrency control framework that uses locks to convert amoebot algorithms that terminate in the sequential setting and satisfy certain conventions into algorithms that exhibit equivalent behavior in the concurrent setting. Together, the canonical amoebot model and these complementary approaches to concurrent algorithm design open new directions for distributed computing research on programmable matter.
BibTeX - Entry
@InProceedings{daymude_et_al:LIPIcs.DISC.2021.20,
author = {Daymude, Joshua J. and Richa, Andr\'{e}a W. and Scheideler, Christian},
title = {{The Canonical Amoebot Model: Algorithms and Concurrency Control}},
booktitle = {35th International Symposium on Distributed Computing (DISC 2021)},
pages = {20:1--20:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-210-5},
ISSN = {1868-8969},
year = {2021},
volume = {209},
editor = {Gilbert, Seth},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14822},
URN = {urn:nbn:de:0030-drops-148227},
doi = {10.4230/LIPIcs.DISC.2021.20},
annote = {Keywords: Programmable matter, self-organization, distributed algorithms, concurrency}
}
|
Keywords: |
|
Programmable matter, self-organization, distributed algorithms, concurrency |
|
Collection: |
|
35th International Symposium on Distributed Computing (DISC 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
04.10.2021 |
