Deterministic Self-Stabilising Leader Election for Programmable Matter with Constant Memory
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918232507547648 |
|---|---|
| author | Chalopin, Jérémie Das, Shantanu Kokkou, Maria |
| author_facet | Chalopin, Jérémie Das, Shantanu Kokkou, Maria |
| contents | The problem of electing a unique leader is central to all distributed systems, including programmable matter systems where particles have constant size memory. In this paper, we present a silent self-stabilising, deterministic, stationary, election algorithm for particles having constant memory, assuming that the system is simply connected. Our algorithm is elegant and simple, and requires constant memory per particle. We prove that our algorithm always stabilises to a configuration with a unique leader, under a daemon satisfying some fairness guarantees (Gouda fairness [Gouda 2001]). We use the special geometric properties of programmable matter in 2D triangular grids to obtain the first self-stabilising algorithm for such systems. This result is surprising since it is known that silent self-stabilising algorithms for election in general distributed networks require $Ω(\log{n})$ bits of memory per node, even for ring topologies [Dolev et al. 1999]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_08775 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Deterministic Self-Stabilising Leader Election for Programmable Matter with Constant Memory Chalopin, Jérémie Das, Shantanu Kokkou, Maria Distributed, Parallel, and Cluster Computing The problem of electing a unique leader is central to all distributed systems, including programmable matter systems where particles have constant size memory. In this paper, we present a silent self-stabilising, deterministic, stationary, election algorithm for particles having constant memory, assuming that the system is simply connected. Our algorithm is elegant and simple, and requires constant memory per particle. We prove that our algorithm always stabilises to a configuration with a unique leader, under a daemon satisfying some fairness guarantees (Gouda fairness [Gouda 2001]). We use the special geometric properties of programmable matter in 2D triangular grids to obtain the first self-stabilising algorithm for such systems. This result is surprising since it is known that silent self-stabilising algorithms for election in general distributed networks require $Ω(\log{n})$ bits of memory per node, even for ring topologies [Dolev et al. 1999]. |
| title | Deterministic Self-Stabilising Leader Election for Programmable Matter with Constant Memory |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2408.08775 |