# Élection auto-stabilisante déterministe pour la matière programmable avec une mémoire constante

Jérémie Chalopin, Shantanu Das, Maria Kokkou

► To cite this version:

Jérémie Chalopin, Shantanu Das, Maria Kokkou. Élection auto-stabilisante déterministe pour la matière programmable avec une mémoire constante. ALGOTEL 2025 – 27èmes Rencontres Franco-phones sur les Aspects Algorithmiques des Télécommunications, Jun 2025, Saint Valery-sur-Somme, France. hal-05030867

HAL Id: hal-05030867

https://hal.science/hal-05030867v1

Submitted on 11 Apr 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Élection auto-stabilisante déterministe pour la matière programmable avec une mémoire constante

Jérémie Chalopin et Shantanu Das et Maria Kokkou

Aix Marseille Univ, CNRS, LIS, 163 Av. de Luminy, 13009, Marseille, France

Le problème de l'élection est une primitive importante pour de nombreux systèmes distribués. Les systèmes de matière programmable sont constitués d'entités computationnelles, appelées particules, qui ont une mémoire de taille constante. Nous considérons des systèmes de matière programmable qui forment un sous-ensemble simplement connexe de la grille triangulaire. Dans ce contexte, nous présentons un algorithme d'élection auto-stabilisant silencieux, déterministe et stationnaire. Notre algorithme est le premier algorithme auto-stabilisant déterministe pour la matière programmable qui élit une particule unique lorsque certaines hypothèses sur l'ordonnanceur sont satisfaites [Gouda, 2001]. Notre résultat est surprenant car dans un réseau arbitraire, tout algorithme d'élection auto-stabilisant silencieux nécessite que chaque nœud ait $\Omega(\log n)$ bits de mémoire [Dolev, 1999].

**Mots-clefs** : Leader Election, Programmable Matter, Self-Stabilisation, Silent, Deterministic, Constant Memory

## 1 Introduction

Programmable Matter (PM) refers to a distributed system consisting of a large number of constant-memory computational entities (called particles) evolving in a geometric environment and acting collaboratively in order to accomplish a given task. Here, we consider the task to be *Leader Election* (LE), that is, distinguishing a unique process in the system as a *leader*. We are interested in deterministic election algorithms that are *self-stabilising*. A distributed algorithm is self-stabilising if when executed on a distributed system in an arbitrary initial configuration, the system eventually reaches a legitimate configuration without external intervention. A self-stabilising algorithm is *silent* if the system always reaches a configuration where the processes no longer change their states. The concept of silent self-stabilising algorithms is also related to *proof-labelling* schemes [KKP10] where each process is given a local certificate to verify certain global properties of the system (e.g., the existence of a unique leader). Each process checks its own certificate and those of its neighbours to verify whether it is in a correct configuration. If the global configuration is incorrect, at least one process detects an inconsistency. We present a silent self-stabilising, deterministic, election algorithm for constant-memory particles, in a simply connected system that always stabilises to a configuration having a unique leader, under a sequential scheduler with fairness guarantees. This work was presented at DISC 2024 [CDK24a] and a complete version can be found on arXiv [CDK24b].

## 2 Model and Preliminaries

Let $G_\Delta$ be an infinite regular triangular grid where each node has six neighbours and let a *particle system* be a subgraph of $G_\Delta$ containing only nodes occupied by particles. A connected particle system, $\mathcal{P}$, is simply connected if $G_\Delta \setminus \mathcal{P}$ is connected (e.g., Figure 1). Each particle is anonymous, has constant memory and has visibility at distance one (i.e., can view the orientation and edges of its neighbours). Each particle has a constant-size memory with arbitrary initial contents. A particle can read the state of each occupied neighbour but can only change the content of its own memory. At each step the scheduler activates one *activable* particle, that is, a particle that changes state after the activation. An execution is *Gouda fair* [DT11, Gou01] if for any configuration $C$ that appears infinitely often in the execution, any successor $C'$ of $C$ also appears infinitely often.
<figure><img src="image_2.png" /><figcaption>Figure 1: Left: A simply connected particle system in $G_A$. Right: The same particle system with broken rules. For each square particle at least one rule is broken and all square particles are activable.</figcaption></figure>

Let $p$ be a particle on the boundary (i.e., a particle with at least one empty neighbour). We say that $p$ is *pending* if $p$ has a unique neighbouring particle in $\mathcal{P}$. We say that $p$ is an *articulation point* if the removal of $p$ disconnects $\mathcal{P}$. If $p$ is neither pending, nor an articulation point, then $p$ is incident to two distinct edges $pq$, $pr$ on the boundary of $\mathcal{P}$. Since $\mathcal{P}$ is simply connected, there is a path of particles in the 1-neighbourhood of $p$ from $q$ to $r$. We say that $p$ is on a $\theta \in \{60^\circ, 120^\circ, 180^\circ, 240^\circ\}$ angle to denote the angle that is formed when moving from $q$ to $r$ around $p$ and no empty nodes are encountered. $\mathcal{P}$ is 2-connected if it does not contain any articulation point. In a 2-connected particle system, Observation 1 implies that there should be a 60° or a 120° particle. Observation 1 is obtained using the fact that the sum of internal angles of a simple polygon with $n$ vertices is $(n-2)\pi$.

**Observation 1.** If $\mathcal{P}$ is 2-connected and $|\mathcal{P}| \ge 3$, particles on the boundary satisfy the formula $2n_{60} + n_{120} - n_{240} = 6$, where $n_\theta$ is the number of $\theta$ particles on the boundary.

From Observation 1 we get the following lemma.

**Lemma 1.** In any simply connected particle system $\mathcal{P}$ with at least two particles, the boundary of $\mathcal{P}$ contains one of following: (i) a pending particle, or (ii) a 60° particle, or (iii) two 120° particles that are connected by a path of 180° particles on the boundary.

### 3 A Proof Labelling Scheme for Leader Election

Our aim is to orient all edges so that a unique sink particle (i.e., particle with no outgoing edges), that we define to be the leader, exists. The certificate given to each particle consists of a direction for each edge incident to the particle. The orientation of the edges is chosen so that particles that are reached by an outgoing edge of some particle $p$, induce a connected graph of size at most three. Each particle $p$ checks that the following rules are locally satisfied or detects an error.

* R1 Each edge is oriented.

* R2 Particle $p$ has at most three outgoing edges.

* R3 When looking at the ports of $p$ cyclically, all outgoing edges of $p$ are consecutive.

* R4 For every 3-particle triangle $p$ belongs in, the triangle is not a directed cycle.

During the execution of the algorithm an edge can be directed or undirected. A particle needs to be able to detect and modify the orientation of edges incident to it, as well as to detect whether it belongs to a 3-particle triangle that is a directed cycle. In this shortened version of our work we assume that particles have these capabilities and refer interested readers to [CDK24b] where we give all details on the implementation of the model. We call a *valid configuration* where every particle satisfies R1–R4 a *valid configuration*. Note that R4 does not guarantee an acyclic orientation (i.e., that larger cycles do not exist in the configuration).

**Theorem 1.** If all rules R1–R4 are satisfied, then there exists a unique sink in the system.

Observe that any particle system admits a valid orientation, that is also acyclic, as it can be constructed from any erosion based Leader Election algorithm for programmable matter (e.g., [DLFS$^+$20, DKMJ21]).
# 4 A Self-Stabilising Algorithm for Leader Election

In Section 3, we claimed that *if* all rules are locally satisfied a unique sink exists in the system. Here, we show *how* a valid configuration is reached from a configuration containing errors. Algorithm 1 is simple: if, when activated, a particle *p* is incident to any number of undirected edges, *p* orients all unoriented edges as outgoing. If this orientation violates a rule, *p* undirects all its outgoing edges.

<table><caption>**Algorithm 1:** Self Stabilising LE</caption><tr><td>If</td><td>¬R1</td><td>:</td><td>Mark all undirected edges as outgoing</td></tr><tr><td>If</td><td>¬R2 ∨ ¬R3 ∨ ¬R4</td><td>:</td><td>Mark all outgoing edges as undirected</td></tr></table>

**Theorem 2.** Starting from an arbitrary simply connected configuration any Gouda fair execution of Algorithm 1 eventually reaches a configuration satisfying R1–R4 in which no rules can be applied and there exists a unique sink.

# 5 Proof Sketch of Theorem 1 and Theorem 2

Notice that the second statement of Theorem 2 is precisely Theorem 1. A configuration of a particle system executing Algorithm 1 is described by the direction of each edge *pq* (i.e., $\vec{pq}$, $\overrightarrow{pq}$ or undirected).

**Observation 2.** Let *p* be a particle such that R3 is satisfied at *p* and let *e*, *e'* be consecutive edges around *p* such that *e* is an incoming edge to *p* and *e'* is an outgoing edge of *p*. If *e* becomes outgoing (resp. *e'* becomes incoming), R3 is not violated at *p*.

**Observation 3.** Let *C* be a configuration and let *p* be a particle so that R1 (resp., R2, R4) is satisfied at some particle *q* ≠ *p* in *C*. Then, R1 (resp., R2, R4) is satisfied at *q* in $C \setminus \{p\}$.

Let $\mathcal{S} = C_0, C_1, \dots$ be an execution of Algorithm 1 starting from a configuration $C_0$. Notice a particle *p* is activable in a configuration *C* if when it executes Algorithm 1, one of its undirected edges becomes outgoing or one of its outgoing edges becomes undirected. If there exists a configuration $C_f$ where no particle is activable, then $C_f = C_j$ for all $j > f$, and we say that the execution stabilises to a final configuration. If all rules are satisfied in this final configuration, then this configuration is valid and we say it is a final directed configuration. If a configuration $C_i$ is not final, we can assume that there exists an activable particle $p_i$ such that we obtain $C_{i+1}$ by activating $p_i$ in $C_i$. Since each particle has constant memory, the number of possible configurations is finite. Hence there exists an index $i_0$ in $\mathcal{S}$ such that any configuration $C_i$ with $i \ge i_0$ appears infinitely often in $\mathcal{S}$ and we write $\mathcal{S}_{i_0}$ to denote the part of the execution starting at $C_{i_0}$. We call the edges that are never undirected in $\mathcal{S}_{i_0}$, stable edges. Notice that any edge $pq$ directed from *p* to *q* in $C_i$ with $i \ge i_0$, is directed from *p* to *q* infinitely often, regardless of whether it is stable.

**Lemma 2.** In any configuration $C_i$ with $i \ge i_0$, Rules R2, R3 and R4 are always satisfied.

*Proof.* Let $n_i$ be the number of particles in $C_i$ that do not satisfy R2, R3 or R4. If a particle *p* is activated in $C_i$, then R2, R3 and R4 are satisfied at *p* in $C_{i+1}$. Moreover, if R2, R3, and R4 are satisfied at some particle *p* in $C_i$ that is not activated at step *i*, then they are still satisfied at step $C_{i+1}$. Consequently, $n_{i+1} \le n_i$. Since for $i \ge i_0$, $C_i$ appears infinitely often, we get that for every $i \ge i_0$, we have $n_i = n_{i_0}$. If $n_i > 0$, there exists a particle *p* that always violates one of the rule R2, R3 or R4. Thus, *p* is eventually activated at some step *i* and in $C_{i+1}$, *p* satisfies the rules, a contradiction. Consequently, for any $i \ge i_0$, R2, R3 and R4 are satisfied at every particle in $C_i$. □

**Lemma 3.** If a particle *p* is incident to a stable outgoing edge, *p* is never activable in $\mathcal{S}_{i_0}$ and all edges incident to *p* are stable edges.

*Proof.* In a configuration $C_i$, if a particle *p* is incident to an outgoing edge and an undirected edge, then *p* is activable. After its activation, either all undirected edges incident to *p* become outgoing, or all outgoing edges of *p* become undirected. Let $\vec{pq}$ be a stable edge, hence, *p* never marks $\vec{pq}$ as undirected. Suppose
that in addition to $\vec{pq}$, $p$ is also incident to an unstable edge $pr$. Then infinitely often, $pr$ is undirected and there exists a step where $p$ is activated and $pr$ is undirected. At this step, $p$ marks $\vec{pr}$ as outgoing. Then, if $\vec{pr}$ becomes undirected at a later step, $\vec{pq}$ must also become undirected, which is a contradiction. $\square$

From Lemmas 2 and 3 we get Lemma 4.

**Lemma 4.** If a particle $p$ is incident to an unstable edge in $\mathcal{S}_{i_0}$, the unstable edges incident to $p$ are at least two and do not appear consecutively around $p$, or there are at least four unstable edges incident to $p$.

The proof of Theorem 2 is done using the structure of the boundary of $\mathcal{P}$ given by Lemma 1. Informally, the proof has the following structure. We assume that it is possible that the system does not stabilise and arrive at a contradiction. Out of the particle systems that do not stabilise to a configuration that satisfies all rules and has a unique sink, we take a system with the minimum number of particles. On the boundary of that system there exists a particle $p$ satisfying one of the cases of Lemma 1. For each orientation of the edges incident to $p$ we show that the edges incident to $p$ are stable. Then we take a smaller system containing exactly one less particle, $p$. We show that the execution in both systems for particles that are not $p$ is the same. Hence, if the system that contains $p$ does not satisfy all rules and does not have a unique sink, the same is true for the system that does not contain $p$. Since we had assumed that the system containing $p$ is the minimum size system that does not stabilise to a valid configuration, a smaller system not stabilising is a contradiction. We only give the detailed proof for the case of a pending particle existing on the boundary.

*Proof of Theorem 2.* Let us suppose that there exists a fair execution $\mathcal{S} = C_0, C_1, \dots$ on a particle configuration $C = C_0$ that does not stabilise to a final directed configuration containing a unique sink. Consider such an execution $\mathcal{S}$ with a support $\mathcal{P}$ of minimum size. As defined above, consider a fair execution $\mathcal{S}_{i_0} = C_{i_0}, C_{i_0+1}, \dots$ containing only configurations appearing infinitely often. By Lemma 1, we can assume that the boundary of $\mathcal{P}$ contains either a pending particle, or a 60° particle, or two 120° particles that are connected by a path of 180° particles on the boundary and we show that each of these cases cannot occur.

**Lemma 5.** If $\mathcal{P}$ contains a pending particle $p$ (i.e., a particle with only one neighbouring particle $w$), all edges are stable in $\mathcal{S}_{i_0}$ and there is a unique sink in the final configuration.

*Proof.* By Lemma 4, the edge $pw$ is stable. Suppose first that $pw$ is directed from $p$ to $w$ in $\mathcal{S}_{i_0}$. For each $i \ge i_0$, let $C'_i = C_i \setminus \{p\}$ and consider the sequence of configurations $\mathcal{S}'_{i_0} = C'_{i_0}, C'_{i_0+1}, \dots, C'_i, \dots$. Observe that for each $i \ge i_0$, either $C_{i+1} = C_i$ or there exists $p_i$ such that $C_{i+1}$ is obtained from $C_i$ by activating $p_i$ and thus modifying the orientations of edges incident to $p_i$. Since $\vec{pw}$ is stable, by Lemma 3, for any $i \ge i_0$, $p_i \ne p$. Moreover, for each $i \ge i_0$, the edges of $C'_i$ have the same orientation as in $C_i$. So, $p' \ne p$ is activable in $C'_i$ if and only if it is activable in $C_i$. Furthermore, the configuration obtained by activating $p_i$ in $C'_i$ is precisely $C'_{i+1}$ since the edges of $C'_i$ have the same orientation as in $C_i$. Hence, $\mathcal{S}'_{i_0}$ is a fair execution of Algorithm 1 on $\mathcal{P} \setminus \{p\}$. By the minimality of the size of $\mathcal{P}$, there exists a step $i$ such that $C'_i$ is a final directed configuration that contains a unique sink $p''$. Since the edges incident to $p$ are stable, $C_i = C_{i_0}$ is a final directed configuration. Since $p$ has an outgoing edge $\vec{pw}$ in $C_{i_0}$, $p''$ is the unique sink of $C_{i_0}$.

Suppose now that $\vec{wp}$ is stable. Notice that in this case, $p$ is a sink in $C_i$ for each $i \ge i_0$. Moreover, since $\vec{wp}$ is stable, by Lemma 3, $w$ is never activated. Since the two common neighbours of $p$ and $w$ are empty, by R3, $p$ is the only outgoing neighbour of $w$ in $C_i$ for any $i \ge i_0$. Consequently, $w$ is a sink in $C_i \setminus \{p\}$ for any $i \ge i_0$. As in the previous case, one can show that $C'_{i_0}$ is a final directed configuration that contains a unique sink $p''$. Since $\vec{wp}$ is stable, $C_{i_0}$ is a final directed configuration. Since any $p' \in C_{i_0} \setminus \{p, w\}$ is not a sink in $C'_{i_0}$, and since $\vec{wp}$ is in $C_{i_0}$, $p$ is the unique sink in the valid configuration $C_{i_0}$. $\square$

**Lemma 6.** If $\mathcal{P}$ contains a 60° particle $p$ or if $\mathcal{P}$ contains two 120° particles $p, p^*$ connected by a path of 180° particles on the boundary, all edges are stable and there is a unique sink in the final configuration.

The proof of Lemma 6 is divided in several cases based on the number and the orientation of the edges incident to $p$. The easiest case is that of $p$ being a source for any number of incident edges. The proof for that case follows the reasoning of the first case of the proof of Lemma 5.

The proof of Theorem 2 follows from Lemmas 1, 5 and 6. $\square$
References

[CDK24a] Jérémie Chalopin, Shantanu Das, and Maria Kokkou. Deterministic Self-Stabilising Leader Election for Programmable Matter with Constant Memory. In *DISC 2024*, volume 319 of *Leibniz International Proceedings in Informatics (LIPIcs)*, pages 13:1–13:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024.

[CDK24b] Jérémie Chalopin, Shantanu Das, and Maria Kokkou. Deterministic self-stabilising leader election for programmable matter with constant memory. *arXiv preprint*, 2024.

[DKMJ21] Fabien Dufoulon, Shay Kutten, and William K. Moses Jr. Efficient deterministic leader election for programmable matter. In *PODC 2021*, pages 103–113. ACM, 2021.

[DLFS+20] Giuseppe Antonio Di Luna, Paola Flocchini, Nicola Santoro, Giovanni Viglietta, and Yukiko Yamauchi. Shape formation by programmable particles. *Distributed Comput.*, 33(1):69–101, 2020.

[DT11] Swan Dubois and Sébastien Tixeuil. A taxonomy of daemons in self-stabilization. *arXiv preprint*, 2011.

[Gou01] Mohamed G. Gouda. The theory of weak stabilization. In *WSS 2001*, volume 2194 of *Lecture Notes in Comput. Sci.*, pages 114–123. Springer, 2001.

[KKP10] Amos Korman, Shay Kutten, and David Peleg. Proof labeling schemes. *Distributed Comput.*, 22(4):215–233, 2010.