DROPS

Document

DOI: 10.4230/LIPIcs.DISC.2024.13

Deterministic Self-Stabilising Leader Election for Programmable Matter with Constant Memory

Authors: Jérémie Chalopin, Shantanu Das, and Maria Kokkou

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)

Abstract

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 [Mohamed G. 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 [Shlomi Dolev et al., 1999].

Cite as

Jérémie Chalopin, Shantanu Das, and Maria Kokkou. Deterministic Self-Stabilising Leader Election for Programmable Matter with Constant Memory. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chalopin_et_al:LIPIcs.DISC.2024.13,
  author =	{Chalopin, J\'{e}r\'{e}mie and Das, Shantanu and Kokkou, Maria},
  title =	{{Deterministic Self-Stabilising Leader Election for Programmable Matter with Constant Memory}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{13:1--13:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.13},
  URN =		{urn:nbn:de:0030-drops-212395},
  doi =		{10.4230/LIPIcs.DISC.2024.13},
  annote =	{Keywords: Leader Election, Programmable Matter, Self-Stabilisation, Silent, Deterministic, Unique Leader, Simply Connected, Gouda fair Daemon, Constant Memory}
}

Search Results

Documents authored by Kokkou, Maria

Deterministic Self-Stabilising Leader Election for Programmable Matter with Constant Memory

Abstract

Cite as

Thanks for your feedback!

Could not send message