Search

International audience; Dans cet article nous considérons les réseaux non anonymes et des problématiques dont la solution peut être capturée par un prédicat booléen Π, problématiques comme la coloration des noeuds, l'élection... Un algorithme auto-stabilisant pour Π est un algorithme distribué qui, quelle que soit la configuration initiale du réseau (c'est-à-dire une configuration où chaque noeud peut se voir attribuer une valeur arbitraire en chacune de ses variables), converge vers une configuration qui satisfait Π. Il est connu que le problème de l'élection n'admet pas d'algorithme déterministe auto-stabilisant utilisant une mémoire constante en bits à chaque noeud, autrement dit, pour certains réseaux, la taille de la mémoire par noeud doit croître en même temps que la taille du réseau. D'autre part, il existe un algorithme déterministe auto-stabilisant pour le problème de l'élection dans un anneau dont la taille mémoire par noeud est O(log log n) bits, où n est la taille du réseau. Nous montrons dans cette article que cette dernière complexité spatiale est optimale. Plus précisément, nous prouvons que tout algorithme déterministe auto-stabilisant résolvant le problème de l'élection doit utiliser une taille mémoire de Ω(log log n) bits par noeud. Nous montrons également que notre borne inférieure s'applique au-delà du problème de l'élection à tous les problèmes qui ne peuvent être résolus par des algorithmes anonymes.

International audience; Nous abordons le problème de la détection de terminaison (TD) dans les réseaux asynchrones. Un algorithme qui résout ce problème détecte si un algorithme distribué observé A a convergé vers une configuration qui satisfait un prédicat particulier. Il est connu que TD ne peut pas être résolu dans le contexte de l'auto-stabilisation, sauf si l'algorithme est instantanément stabilisant (snap-stabilization), c'est-à-dire qu'il se comporte toujours conformément à sa spécification, indépendamment de la configuration initiale. Un algorithme déterministe instantanément stabilisant pour TD est donné dans [7] pour les réseaux enracinés, autrement dit les réseaux où tous les noeuds exécutent le même algorithme, sauf un. Dans cet article, nous proposons un algorithme générique, déterministe, silencieux, instantanément stabilisant, qui détecte la terminaison d'un algorithme observé A, auto-stabilisant, silencieux et terminant. Notre algorithme ne nécessite pas de structure sous-jacente, ni de topologie spécifique et fonctionne dans des réseaux anonymes. Plus précisément notre algorithme n'utilise aucune hypothèse permettant de distinguer un ou plusieurs processus, de plus, il fonctionne sous les hypothèses de l'ordonnanceur le plus faible, l'ordonnanceur inéquitable. Construite audessus de n'importe quel unisson asynchrone auto-stabilisant sous-jacent U, notre solution requiert comme espace mémoire supplémentaire uniquement O(log D) bits par noeud, où D est le diamètre du réseau. Puisqu'il n'existe aucun algorithme d'unisson avec une meilleure complexité spatiale, l'espace mémoire supplémentaire de notre solution est comparable à la complexité spatiale de l'algorithme d'unisson sous-jacent. Notre algorithme fournit une réponse positive en O(max(k, k' , D)) rounds, où k et k' sont les complexités respectives en temps de stabilisation de A et U.