Soutenance de thèse de KOKKOU Maria
Titre de thèse
Élection auto-stabilisante et tolérante aux pannes dans les systèmes de matière programmable
Self-Stabilising and Fault Tolerant Leader Election in Programmable Matter Systems
Résumé de la thèse
Dans cette thèse, nous analysons le problème de l'élection dans le cadre du paradigme de la matière programmable, dans un contexte tolérant aux pannes. La matière programmable fait référence à des entités computationnelles limitées (appelées "particules") qui agissent dans un environnement géométrique, possèdent une mémoire constante et peuvent changer leurs propriétés physiques de manière programmable. L'élection est une primitive importante pour la matière programmable, car elle constitue souvent une étape intermédiaire pour la résolution de problèmes plus complexes. Bien que le problème de l'élection soit très étudié, même dans le contexte spécifique des systèmes de matière programmable, les recherches sur les approches tolérantes aux pannes sont plus limitées. Nous considérons le problème dans le modèle Amoebot précédemment étudié, principalement pour des configurations de particules placées sur des grilles triangulaires et, secondairement, sur des grilles carrées et cubiques. L'objectif principal de cette thèse est de proposer des algorithmes auto-stabilisant, c'est-à-dire des algorithmes qui doivent fonctionner même si la configuration initiale est initialisée de manière arbitraire.
Nous commençons par aborder le problème dans un cadre non auto-stabilisant. Dans ce cas, nous supposons que les particules s'accordent sur les directions le long d'un axe de la grille triangulaire et montrons qu'un algorithme d'élection avec une terminaison explicite n'est pas possible dans ce cas. Ainsi, nous proposons un algorithme à terminaison implicite qui élit une particule unique sans nécessiter aucun mouvement. Résoudre le problème sous l'hypothèse d'une direction commune permet d'élire une particule unique de manière stationnaire et déterministe, ce qui n'était jusqu'alors possible que pour des configurations simplement connexes avec un ordonnanceur séquentiel.
Nous abordons ensuite le problème dans un cadre auto-stabilisant sous deux hypothèses principales : les particules forment une configuration simplement connexe et les particules forment une configuration connexe. Dans le premier cas, nous définissons un ensemble local de conditions telles que, si toutes les conditions sont vraies pour chaque particule, alors il existe une particule élue unique dans le système. Nous utilisons cet ensemble de règles (appelé un "certificat") pour créer le premier algorithme qui résout l'élection de manière auto-stabilisante pour les systèmes de matière programmable, sous certaines hypothèses d'équité. Dans le second cas, nous utilisons le mouvement des particules pour dériver directement un algorithme auto-stabilisant qui fonctionne même sous un ordonnanceur non équitable.
Enfin, nous considérons les grilles carrées et cubiques et nous donnons le premier résultat d'élection auto-stabilisant pour la matière programmable dans le cas tridimensionnel. En particulier, nous montrons d'abord comment on peut, à partir d'un certificat, dériver un algorithme auto-stabilisant non déterministe qui est correct avec un ordonnanceur équitable, au sens de Gouda. Nous définissons ensuite un certificat qui fonctionne dans le cas bidimensionnel et dans un cadre spécifique mais non trivial dans le cas tridimensionnel.
Thesis resume
In this thesis we study the problem of Leader Election within the programmable matter paradigm in a fault tolerant context. Programmable matter refers to limited computational entities (called "particles") that act in a geometric environment, have constant memory and can change their physical properties in a programmable way. Leader election is an important primitive for programmable matter, since it is often an intermediate step for the solution of more complex problems. Although the leader election problem itself is well studied even in the specific context of programmable matter systems, research on fault tolerant approaches is more limited. We consider the problem in the previously studied Amoebot model mainly for particle configurations embedded on triangular grids and, secondarily, on square and cubical grids. The main focus of this thesis is self--stabilising algorithms, that is, algorithms that need to work even if the initial configuration is arbitrarily initialised.
We begin by addressing the problem in a non self-stabilising setting. In this case, we assume that particles agree on the directions along one axis of the triangular grid and show that an election algorithm with explicit termination is not possible in this case. Hence, we provide an implicitly terminating algorithm that elects a unique leader without requiring any movement. Solving the problem under the assumption of one common direction allows for a unique leader to be elected in a stationary and deterministic way, which until now was only possible for simply connected configurations under a sequential scheduler.
Then we address the problem in a self-stabilising setting under two main assumptions: the particles form a simply connected configuration and the particles form a connected configuration. In the former case, we define a local set of conditions such that if all conditions are true for every particle, then there exists a unique leader in the system. We use this set of rules (called a "certificate") to create the first algorithm that solves leader election in a self--stabilising way for programmable matter systems, under some fairness assumptions. In the latter case, we use movement of particles to directly derive a self-stabilising algorithm that works even under an unfair scheduler.
Finally, we consider square and cubical grids and we give the first self-stabilising leader election result for programmable matter in the three dimensional case. In particular, we first show how to derive a non-deterministic, self-stabilising algorithm that is correct under a Gouda fair scheduler, given a certificate. Then we define a certificate that works in the two dimensional case and in a specific but non-trivial setting in the three dimensional case.