Silent Self-Stabilising Leader Election in Programmable Matter Systems with Holes
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912955892760576 |
|---|---|
| author | Chalopin, Jérémie Das, Shantanu Kokkou, Maria |
| author_facet | Chalopin, Jérémie Das, Shantanu Kokkou, Maria |
| contents | Leader election is a fundamental problem in distributed computing, particularly within programmable matter systems, where coordination among simple computational entities is crucial for solving complex tasks. In these systems, particles (i.e., constant-memory computational entities) operate in a regular triangular grid as described in the geometric Amoebot model. While leader election has been extensively studied in non self-stabilising settings, self-stabilising solutions remain more limited. In this work, we study the problem of self-stabilising leader election in connected (but not necessarily simply connected) configurations. We present the first self-stabilising algorithm for connected programmable matter systems that guarantees the election of a unique leader under an unfair scheduler, for oblivious particles (i.e., particles with no persistent memory) that share a common sense of direction. Our approach leverages particle movement, a capability not previously exploited in the self-stabilising context. We show that movement in conjunction with particles sharing a sense of orientation and operating in a grid can overcome classical impossibility results for constant-memory systems established by Dolev, Gouda and Schneider (1999). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_20201 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Silent Self-Stabilising Leader Election in Programmable Matter Systems with Holes Chalopin, Jérémie Das, Shantanu Kokkou, Maria Distributed, Parallel, and Cluster Computing Leader election is a fundamental problem in distributed computing, particularly within programmable matter systems, where coordination among simple computational entities is crucial for solving complex tasks. In these systems, particles (i.e., constant-memory computational entities) operate in a regular triangular grid as described in the geometric Amoebot model. While leader election has been extensively studied in non self-stabilising settings, self-stabilising solutions remain more limited. In this work, we study the problem of self-stabilising leader election in connected (but not necessarily simply connected) configurations. We present the first self-stabilising algorithm for connected programmable matter systems that guarantees the election of a unique leader under an unfair scheduler, for oblivious particles (i.e., particles with no persistent memory) that share a common sense of direction. Our approach leverages particle movement, a capability not previously exploited in the self-stabilising context. We show that movement in conjunction with particles sharing a sense of orientation and operating in a grid can overcome classical impossibility results for constant-memory systems established by Dolev, Gouda and Schneider (1999). |
| title | Silent Self-Stabilising Leader Election in Programmable Matter Systems with Holes |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2507.20201 |