Search Results

Documents authored by Navarra, Alfredo

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}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2007.1175
12. Robust Algorithms and Price of Robustness in Shunting Problems

Authors: Serafino Cicerone, Gianlorenzo D'Angelo, Gabriele Di Stefano, Daniele Frigioni, and Alfredo Navarra

Published in: OASIcs, Volume 7, 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07) (2007)

Abstract
In this paper we provide efficient robust algorithms for shunting problems concerning the reordering of train cars over a hump. In particular, we study algorithms able to cope with small disruptions, as temporary and local availability and/or malfunctioning of key resources that can occur and affect planned operations. To this aim, a definition of robust algorithm is provided. Performances of the proposed algorithms are measured by the notion of price of robustness. Various scenarios are considered, and interesting results are presented.
Cite as

Serafino Cicerone, Gianlorenzo D'Angelo, Gabriele Di Stefano, Daniele Frigioni, and Alfredo Navarra. 12. Robust Algorithms and Price of Robustness in Shunting Problems. In 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07). Open Access Series in Informatics (OASIcs), Volume 7, pp. 175-190, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{cicerone_et_al:OASIcs.ATMOS.2007.1175,
  author =	{Cicerone, Serafino and D'Angelo, Gianlorenzo and Di Stefano, Gabriele and Frigioni, Daniele and Navarra, Alfredo},
  title =	{{12. Robust Algorithms and Price of Robustness in Shunting Problems}},
  booktitle =	{7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
  pages =	{175--190},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-04-0},
  ISSN =	{2190-6807},
  year =	{2007},
  volume =	{7},
  editor =	{Ahuja, Ravindra K. and Liebchen, Christian and Mesa, Juan A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007.1175},
  URN =		{urn:nbn:de:0030-drops-11755},
  doi =		{10.4230/OASIcs.ATMOS.2007.1175},
  annote =	{Keywords: }
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact