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.

International audience; Nous explorons la possibilité de concevoir des algorithmes auto-stabilisants pour des systèmes distribués à passage de messages où l'adversaire peut initialement placer un nombre arbitraire de messages corrompus (leur contenu est également déterminé par l'adversaire) dans les canaux de communications. Plus précisément, nous proposons un algorithme auto-stabilisant de (∆ + 1)-coloration pour un graphe arbitraire de degré maximum ∆ dans le modèle à passage de messages asynchrone. Cet algorithme est déterministe et converge en O(k ∆ n 2 log n) échanges de messages, où k est une borne sur la capacité des canaux de communications et n est le nombre de processus. Notre algorithme utilise des messages de O(log log n + log ∆) bits et une mémoire de O(∆ log ∆ + log log n) bits par processus. La propriété fondamentale de notre algorithme est le fait que les processus ne nécessitent aucune connaissance sur le nombre de messages initialement présents dans les canaux (k est inconnu). Pour concevoir notre protocole de coloration, nous utilisons une construction auto-stabilisante de graphe orienté acyclique couvrant, qui peut également servir d'outil pour résoudre d'autres tâches dans le même contexte.

In the context of self-stabilization, a silent algorithm guarantees that the communication registers (a.k.a register) of every node do not change once the algorithm has stabilized. At the end of the 90's, Dolev et al. [Acta Inf. '99] showed that, for finding the centers of a graph, for electing a leader, or for constructing a spanning tree, every silent deterministic algorithm must use a memory of Omega(log n) bits per register in n-node networks. Similarly, Korman et al. [Dist. Comp. '07] proved, using the notion of proof-labeling-scheme, that, for constructing a minimum-weight spanning tree (MST), every silent algorithm must use a memory of Omega(log^2n) bits per register. It follows that requiring the algorithm to be silent has a cost in terms of memory space, while, in the context of self-stabilization, where every node constantly checks the states of its neighbors, the silence property can be of limited practical interest. In fact, it is known that relaxing this requirement results in algorithms with smaller space-complexity. In this paper, we are aiming at measuring how much gain in terms of memory can be expected by using arbitrary deterministic self-stabilizing algorithms, not necessarily silent. To our knowledge, the only known lower bound on the memory requirement for deterministic general algorithms, also established at the end of the 90's, is due to Beauquier et al. [PODC '99] who proved that registers of constant size are not sufficient for leader election algorithms. We improve this result by establishing the lower bound Omega(log log n) bits per register for deterministic self-stabilizing algorithms solving (Delta+1)-coloring, leader election or constructing a spanning tree in networks of maximum degree Delta.

International audience; Nous présentons le premier algorithme auto-stabilisant d'´ election pour les réseaux de topologie arbitraire dont la complexité en espace est de O(max{log ∆, log log n}) bits par noeud, o` u n est la taille du réseau et ∆ son degré. Cette complexité en espace est sous-logarithmique en n, tant que ∆ = n o(1) .

International audience; We present a self-stabilizing leader election algorithm for general networks, with space-complexity $O(\max\{\log \Delta, \log \log n\})$ bits per node in $n$-node networks with maximum degree~$\Delta$. This space complexity is sub-logarithmic in $n$ as long as $\Delta = n^{o(1)}$. The best space-complexity known so far for general networks was $O(\log n)$ bits per node, and algorithms with sub-logarithmic space-complexities were known for the ring only. To our knowledge, our algorithm is the first algorithm for self-stabilizing leader election to break the $\Omega(\log n)$ bound for silent algorithms in general networks. Breaking this bound was obtained via the design of a (non-silent) self-stabilizing algorithm using sophisticated tools such as solving the distance-2 coloring problem in a silent self-stabilizing manner, with space-complexity $O(\max\{\log \Delta, \log \log n\})$ bits per node. Solving this latter coloring problem allows us to implement a sub-logarithmic encoding of spanning trees --- storing the IDs of the neighbors requires $\Omega(\log n)$ bits per node, while we encode spanning trees using $O(\max\{\log \Delta, \log \log n\})$ bits per node. Moreover, we show how to construct such compactly encoded spanning trees without relying on variables encoding distances or number of nodes, as these two types of variables would also require $\Omega(\log n)$ bits per node.

We present the first self-stabilizing algorithm for leader election in arbitrary topologies whose space complexity is O(max{log Delta, log log n}) bits per node, where n is the network size and Delta its degree. This complexity is sub-logarithmic in n when Delta = n^o(1).

International audience; Le diamètre est l'un des paramètres les plus importants dans les réseaux. Calculer le diamètre d'un réseau est un problème fondamental dans l'analyse des réseaux à large échelle. De plus, cette métrique est utilisée dans d'importants domaines d'application dans les réseaux réels. Par conséquent, il est naturel d'étudier ce problème dans un réseau distribué, et plus généralement dans un réseau distribué tolérant aux fautes transitoires. Plus précisément, nous nous sommes intéressés au problème de l'identification d'un centre d'un graphe. Une fois trouvé, nous construisons un arbre couvrant de diamètre minimum enraciné sur ce centre. Ainsi, le problème principal revient à calculer le centre d'un graphe. Dans cet article, nous présentons un algorithme auto-stabilisant uniforme pour le problème de construction d'un arbre couvrant de diamètre minimum dans le modèle à états. Notre algorithme possède plusieurs avantages qui le rendent adapté à des fins pratiques. C'est le premier algorithme traitant ce problème qui opère sous un démon non équitable (environnement asynchrone). En d'autres termes, aucune restriction n'est faite sur le comportement distribué du réseau. Par conséquent, c'est le démon le plus difficile avec lequel le réseau peut composer. De plus, notre algorithme utilise une mémoire de O(\log n) bits par processus (ou n est le nombre de processus). Cet algorithme améliore les résultats précédents d'un facteur n. Ces améliorations ne sont pas atteintes au détriment du temps de convergence, qui reste polynomial en nombre de rondes.

National audience