In the distributed model Amoebot of programmable matter, the computational entities, called particles, are anonymous finite-state machines that operate and move on a hexagonal tessellation of the plane. In this paper we show how a constant number of such weak particles can simulate a powerful Turing-complete entity that is able to move on the plane while computing. We then show an application of our tool to the classical Shape-Formation problem, providing a new and much more general distributed solution. Indeed, while the existing algorithms allow to form only shapes made of arrangements of segments and triangles, our algorithm allows the particles to form also more abstract and general connected shapes, including circles and spirals, as well as fractal objects of non-integer dimension. In lieu of the existing impossibility results based on the symmetry of the initial configuration of the particles, our result provides a complete characterization of the connected shapes that can be formed by an initially simply connected set of particles. Furthermore, in the case of non-connected target shapes, we give almost-matching necessary and sufficient conditions for their formability.
Mobile RAM and shape formation by programmable particles / Di Luna, G. A.; Flocchini, P.; Santoro, N.; Viglietta, G.; Yamauchi, Y.. - 12247:(2020), pp. 343-358. (Intervento presentato al convegno International European Conference on Parallel and Distributed Computing (was International Conference on Parallel Processing) tenutosi a Warsaw) [10.1007/978-3-030-57675-2_22].
Mobile RAM and shape formation by programmable particles
Di Luna G. A.
;
2020
Abstract
In the distributed model Amoebot of programmable matter, the computational entities, called particles, are anonymous finite-state machines that operate and move on a hexagonal tessellation of the plane. In this paper we show how a constant number of such weak particles can simulate a powerful Turing-complete entity that is able to move on the plane while computing. We then show an application of our tool to the classical Shape-Formation problem, providing a new and much more general distributed solution. Indeed, while the existing algorithms allow to form only shapes made of arrangements of segments and triangles, our algorithm allows the particles to form also more abstract and general connected shapes, including circles and spirals, as well as fractal objects of non-integer dimension. In lieu of the existing impossibility results based on the symmetry of the initial configuration of the particles, our result provides a complete characterization of the connected shapes that can be formed by an initially simply connected set of particles. Furthermore, in the case of non-connected target shapes, we give almost-matching necessary and sufficient conditions for their formability.File | Dimensione | Formato | |
---|---|---|---|
DiLuna_preprint_Mobile-RAMA_2020.pdf
accesso aperto
Note: https://link.springer.com/chapter/10.1007/978-3-030-57675-2_22
Tipologia:
Documento in Pre-print (manoscritto inviato all'editore, precedente alla peer review)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
541.39 kB
Formato
Adobe PDF
|
541.39 kB | Adobe PDF | |
DiLuna_Mobile-RAMA_2020.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
447.86 kB
Formato
Adobe PDF
|
447.86 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.