We study models and algorithms for Programmable Matter (PM, shortly), that is matter with the ability to change its physical properties (e.g., shape or optical properties) in a programmable fashion. PM can be implemented by assembling a system of weak self-organizing computational elements, called particles, that can be programmed via distributed algorithms to collectively achieve some global task. We first introduce SILBOT, a new and weak modeling approach that, unlike previous ones, does not require: i) any synchronization mechanism nor explicit communication between particles; ii) atomicity for the performed actions; iii) activation of one particle per time within a finite neighborhood. Second, we present a distributed algorithm to solve, in the SILBOT model, a foundational primitive for PM, namely Leader Election. This algorithm manages initial configurations that are both connected (i.e. particles induce a connected graph) and compact (i.e. without holes). Third, we show that, if the initial configuration contains holes, it is impossible to achieve leader election while preserving connectivity. Finally, we design an algorithm to handle configurations admitting holes. Specifically, the algorithm achieves compaction, i.e. stabilizes the system into a compact connected configuration, while at the same time accomplishing leader election, provided that particles are able to sense holes.

Leader election and compaction for asynchronous silent programmable matter

D'Angelo, G.;
2020-01-01

Abstract

We study models and algorithms for Programmable Matter (PM, shortly), that is matter with the ability to change its physical properties (e.g., shape or optical properties) in a programmable fashion. PM can be implemented by assembling a system of weak self-organizing computational elements, called particles, that can be programmed via distributed algorithms to collectively achieve some global task. We first introduce SILBOT, a new and weak modeling approach that, unlike previous ones, does not require: i) any synchronization mechanism nor explicit communication between particles; ii) atomicity for the performed actions; iii) activation of one particle per time within a finite neighborhood. Second, we present a distributed algorithm to solve, in the SILBOT model, a foundational primitive for PM, namely Leader Election. This algorithm manages initial configurations that are both connected (i.e. particles induce a connected graph) and compact (i.e. without holes). Third, we show that, if the initial configuration contains holes, it is impossible to achieve leader election while preserving connectivity. Finally, we design an algorithm to handle configurations admitting holes. Specifically, the algorithm achieves compaction, i.e. stabilizes the system into a compact connected configuration, while at the same time accomplishing leader election, provided that particles are able to sense holes.
2020
978-1-4503-7518-4
Programmable Matter; Swarm Robotics; Self-Organizing Systems; Leader Election; Compaction; Finite Automata; Distributed Algorithms.
File in questo prodotto:
File Dimensione Formato  
PostPrint_2020_19thAAMAS_276_DAngelo.pdf

accesso aperto

Tipologia: Documento in Post-print
Licenza: Creative commons
Dimensione 512.98 kB
Formato Adobe PDF
512.98 kB Adobe PDF Visualizza/Apri
2020_19thAAMAS_276_DAngelo.pdf

non disponibili

Tipologia: Versione Editoriale (PDF)
Licenza: Copyright dell'editore
Dimensione 1 MB
Formato Adobe PDF
1 MB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.12571/24535
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 15
  • ???jsp.display-item.citation.isi??? ND
social impact