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.SAND.2022.23
URN: urn:nbn:de:0030-drops-159656
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15965/
Go to the corresponding LIPIcs Volume Portal

Kostitsyna, Irina ; Scheideler, Christian ; Warner, Daniel

Brief Announcement: Fault-Tolerant Shape Formation in the Amoebot Model

pdf-format:
LIPIcs-SAND-2022-23.pdf (4 MB)

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 propose a new model 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 propose 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.SAND.2022.23,
  author =	{Kostitsyna, Irina and Scheideler, Christian and Warner, Daniel},
  title =	{{Brief Announcement: Fault-Tolerant Shape Formation in the Amoebot Model}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{23:1--23:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15965},
  URN =		{urn:nbn:de:0030-drops-159656},
  doi =		{10.4230/LIPIcs.SAND.2022.23},
  annote =	{Keywords: Programmable matter, Geometric amoebot model, Fault tolerance, Shape formation}
}

Keywords: Programmable matter, Geometric amoebot model, Fault tolerance, Shape formation
Collection: 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)
Issue Date: 2022
Date of publication: 29.04.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI