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.DNA.28.9
URN: urn:nbn:de:0030-drops-167949
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16794/
Kostitsyna, Irina ;
Scheideler, Christian ;
Warner, Daniel
Fault-Tolerant Shape Formation in the Amoebot Model
Abstract
The amoebot model is a distributed computing model of programmable matter. It envisions programmable matter as a collection of computational units called amoebots or particles that utilize local interactions to achieve tasks of coordination, movement and conformation. In the geometric amoebot model the particles operate on a hexagonal tessellation of the plane. Within this model, numerous problems such as leader election, shape formation or object coating have been studied. One area that has not received much attention so far, but is highly relevant for a practical implementation of programmable matter, is fault tolerance. The existing literature on that aspect allows particles to crash but assumes that crashed particles do not recover. We proposed a new model [Kostitsyna et al., 2022] in which a crash causes the memory of a particle to be reset and a crashed particle can detect that it has crashed and try to recover using its local information and communication capabilities. We present an algorithm that solves the hexagon shape formation problem in our model if a finite number of crashes occur and a designated leader particle does not fail. At the heart of our solution lies a fault-tolerant implementation of the spanning forest primitive, which, since other algorithms in the amoebot model also make use of it, is also of general interest.
BibTeX - Entry
@InProceedings{kostitsyna_et_al:LIPIcs.DNA.28.9,
author = {Kostitsyna, Irina and Scheideler, Christian and Warner, Daniel},
title = {{Fault-Tolerant Shape Formation in the Amoebot Model}},
booktitle = {28th International Conference on DNA Computing and Molecular Programming (DNA 28)},
pages = {9:1--9:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-253-2},
ISSN = {1868-8969},
year = {2022},
volume = {238},
editor = {Ouldridge, Thomas E. and Wickham, Shelley F. J.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16794},
URN = {urn:nbn:de:0030-drops-167949},
doi = {10.4230/LIPIcs.DNA.28.9},
annote = {Keywords: programmable matter, amoebot model, fault tolerance, shape formation}
}
