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.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.