2026-08-06T04:46:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19515 2024-03-06T11:04:12Z ddc:004 open_access

Silent Programmable Matter: Coating Navarra, Alfredo Piselli, Francesco Programmable Matter Coating Asynchrony Stigmergy 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alfredo Navarra and Francesco Piselli 2024 Is Part Of LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2023.25 urn:nbn:de:0030-drops-195150 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.25 eng https://creativecommons.org/licenses/by/4.0/legalcode