Search

International audience; La M-exclusion a pour but de partager L ressources identiques. Elle est définie par trois propriétés : l'équité, la sûreté et une propriété d'efficacité appelée évitement de L-interblocage. Nous montrons que tout algorithme réalisant ces trois propriétés a un temps d'attente en Omega(n-L) rondes dans un anneau de n processus. Donc, quand n est grand comparé à L, le gain d'avoir L ressources identiques au lieu d'une seule devient négligeable. Pour contourner ce problème, nous reformulons la définition de L-exclusion en remplaçant la propriété d'évitement de L-interblocage par une contrainte sur le temps d'attente. Nous illustrons cette nouvelle version du problème avec des algorithmes autostabilisants dont le temps d'attente est en O(n/L) rondes, la borne asymptotique optimale.

International audience; Nous proposons un algorithme distribué, autostabilisant et silencieux avec convergence sûre qui calcule une \fga minimale dans un réseau asynchrone identifié, où $f$ et $g$ sont deux fonctions associant à chaque n\oe ud un entier positif ou nul qui vérifient~: pour tout n\oe ud $p$, $f(p) \geq g(p)$ et $\delta_p \geq g(p)$, où $\delta_p$ est le degré du n\oe ud $p$ dans le réseau.

International audience; In this paper, we address the deterministic rendezvous in graphs where k mobile agents, disseminated at different times and different nodes, have to meet in finite time at the same node. The mobile agents are autonomous, oblivious, labeled, and move asynchronously. Moreover, we consider an undirected anonymous connected graph. For this problem, we exhibit some asymptotical time and space lower bounds as well as some necessary conditions. We also propose an algorithm that is asymptotically optimal in both space and round complexities.

International audience; In this paper, we address the deterministic rendezvous of mobile agents into any unoriented connected graph. The agents are autonomous, oblivious, move asynchronously. For this problem, we exhibit some time and space lower bounds as well as some necessary conditions. We also propose an algorithm that is space-optimal and asymptotically optimal in rounds.

This thesis deals with the self-stabilizing construction of spanning structures over a distributed system. Self-stabilization is a paradigm for fault-tolerance in distributed algorithms. It guarantees that the system eventually satisfies its specification after transient faults hit the system. Our model of distributed system assumes locally shared memories for communicating, unique identifiers for symmetry-breaking, and distributed daemon for execution scheduling, that is, the weakest proper daemon. More generally, we aim for the weakest possible assumptions, such as arbitrary topologies, in order to propose the most versatile constructions of distributed spanning structures. We present four original self-stabilizing algorithms achieving k-clustering, (f,g)-alliance construction, and ranking. For every of these problems, we prove the correctness of our solutions. Moreover, we analyze their time and space complexity using formal proofs and simulations. Finally, for the (f,g)-alliance problem, we consider the notion of safe convergence in addition to self-stabilization. It enforces the system to first quickly satisfy a specification that guarantees a minimum of conditions, and then to converge to a more stringent specification., Cette thèse s'intéresse à la construction auto-stabilisante de structures couvrantes dans un système réparti. L'auto-stabilisation est un paradigme pour la tolérance aux fautes dans les algorithmes répartis. Plus précisément, elle garantit que le système retrouve un comportement correct en temps fini après avoir été perturbé par des fautes transitoires. Notre modèle de système réparti se base sur des mémoires localement partagées pour la communication, des identifiants uniques pour briser les symétries et un ordonnanceur inéquitable, c'est-à-dire le plus faible des ordonnanceurs. Dans la mesure du possible, nous nous imposons d'utiliser les plus faibles hypothèses, afin d'obtenir les constructions les plus générales de structures couvrantes réparties. Nous présentons quatre algorithmes auto-stabilisants originaux pour le k-partitionnement, la construction d'une (f,g)-alliance et l'indexation. Pour chacun de ces problèmes, nous prouvons la correction de nos solutions. De plus, nous analysons leur complexité en temps et en espace à l'aide de preuves formelles et de simulations. Enfin, pour le problème de (f,g)-alliance, nous prenons en compte la notion de convergence sûre qui vient s'ajouter à celle d'auto-stabilisation. Elle garantit d'abord que le comportement du système assure rapidement un minimum de conditions, puis qu'il continue de converger jusqu'à se conformer à une spécification plus exigeante.