DROPS

Document

DOI: 10.4230/LIPIcs.OPODIS.2023.25

Silent Programmable Matter: Coating

Authors: Alfredo Navarra and Francesco Piselli

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

Abstract

By Programmable Matter (PM) is usually meant a system of weak and self-organizing computational entities, called particles, which can be programmed via distributed algorithms to collectively achieve some global tasks. We consider the SILBOT model where particles are modeled as finite state automata, living and operating in the cells of a hexagonal grid. Particles are all identical, executing the same deterministic algorithm which is based on local observation of the surroundings, up to two hops. Particles are asynchronous, without any direct means of communication and disoriented but sharing a common handedness, i.e., chirality is assumed. Within such a basic model, we consider a foundational primitive for PM, that is Coating: a set of n particles must move so as to ensure the closed surrounding of an object occupying some connected cells of the grid. We present an optimal deterministic distributed algorithm - along with the correctness proof, that in Θ(n²) rounds solves the Coating problem, where a round concerns the minimal time window within which each particle is activated at least once.

Cite as

Alfredo Navarra and Francesco Piselli. Silent Programmable Matter: Coating. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{navarra_et_al:LIPIcs.OPODIS.2023.25,
  author =	{Navarra, Alfredo and Piselli, Francesco},
  title =	{{Silent Programmable Matter: Coating}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-308-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{286},
  editor =	{Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.25},
  URN =		{urn:nbn:de:0030-drops-195150},
  doi =		{10.4230/LIPIcs.OPODIS.2023.25},
  annote =	{Keywords: Programmable Matter, Coating, Asynchrony, Stigmergy}
}

Document

Brief Announcement

DOI: 10.4230/LIPIcs.DISC.2023.45

Brief Announcement: Line Formation in Silent Programmable Matter

Authors: Alfredo Navarra and Francesco Piselli

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

Abstract

Programmable Matter (PM) has been widely investigated in recent years. One reference model is certainly Amoebot, with its recent canonical version (DISC 2021). Along this line, with the aim of simplification and to address concurrency, the SILBOT model has been introduced (AAMAS 2020). Within SILBOT, we consider the Line formation primitive in which particles are required to end up in a configuration where they are all aligned and connected. We propose a simple and elegant distributed algorithm, optimal in terms of number of movements.

Cite as

Alfredo Navarra and Francesco Piselli. Brief Announcement: Line Formation in Silent Programmable Matter. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 45:1-45:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{navarra_et_al:LIPIcs.DISC.2023.45,
  author =	{Navarra, Alfredo and Piselli, Francesco},
  title =	{{Brief Announcement: Line Formation in Silent Programmable Matter}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{45:1--45:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.45},
  URN =		{urn:nbn:de:0030-drops-191715},
  doi =		{10.4230/LIPIcs.DISC.2023.45},
  annote =	{Keywords: Programmable Matter, Line formation, Asynchrony, Stigmergy}
}

Search Results

Documents authored by Piselli, Francesco

Silent Programmable Matter: Coating

Abstract

Cite as

Brief Announcement: Line Formation in Silent Programmable Matter

Abstract

Cite as

Thanks for your feedback!

Could not send message