Search

Avec la complexification et la multiplication du nombre de composants dans les réseaux informatiques, la vulnérabilité aux défaillances temporaires s'est accentuée dans ces derniers. Avoir un système apte à résister à ces pannes transitoires et capable de retrouver rapidement un fonctionnement correct est un véritable défi qui peut être appréhendé à l'aide du concept d'autostabilisation...

The work presented in this thesis can be divided in two, the first part focusing on self-stabilization in distributed systems, and the second one on classical graph algorithms.The self-stabilization part deals with Byzantine faults for problems that had no prior algorithm handling those. One of them is then used to propose a way to produce self-stabilizing algorithms for mendable problems in anonymous networks. The classical graph algorithm part introduces a new problem that extends some previous work on colored matchings and gives a hardness results as well as an FPT algorithm for a specific parameter.Chapter 3 introduces an algorithm that handles Byzantine faults and solves the MIS problem in anonymous systems in O(n²) rounds with high probability under the fair distributed daemon. It then gives a slightly modified version of this algorithm, that solves the same problem under the adversarial distributed daemon (without handling Byzantine faults) in O(n²) moves.Chapter 5 introduces an algorithm that handles Byzantine faults and solves the Minimal Clique Decomposition problem in O(Δn) rounds under the fair distributed daemon in systems with unique identifiers.Chapter 4 introduces an algorithm that solves the (k,k-1)-ruling set problem in anonymous networks under the Gouda daemon. The parallel construction of multiple such ruling sets allows to find a distance-K coloring in an anonymous network, whose colors are used as identifiers to solve any mending problems on anonymous networks.Finally, Chapter 6 introduces a new problem, the Minimum Colored Maximum Matching problem, that extends what had already been done on colored matchings. The problem is shown to be NP-hard and hard to approximate within a logarithmic ratio of the size of the graph. It is also proven W[2]-hard with the parameter "size of the solution", but fixed-parameter tractable with the parameter "size of a maximum matching".; Le travail présenté par cette thèse peut être divisé en deux parties, la première se concentrant sur l'autostabilisation dans des systèmes distribués, la seconde sur de l'algorithmique de graphe classique. La partie portant sur l'autostabilisation s'intéresse aux pannes Byzantines pour des problèmes qui n'avaient pas d'algorithme connu supportant celles-ci. L'un d'eux est ensuite utilisé pour proposer un mécanisme produisant des algorithme autostabilisants pour tout problème raccommodable dans des réseaux anonymes. La partie d'algorithmique de graphes introduit a nouveau problème étendant des travaux antérieurs sur les couplages colorés et donne un résultat de difficulté algorithmique ainsi qu'un algorithme FPT pour un certain paramètre.Le chapitre 3 introduit un algorithme qui supporte les pannes Byzantines et résout le problème de l'indépendant maximal dans les systèmes anonymes en O(n²) rounds avec forte probabilité sous le démon distribué juste. Il donne ensuite une version légèrement modifiée de cet algorithme qui résout le même problème sous le démon distribué antagoniste (sans supporter de pannes Byzantines) en O(n²) opérations.Le chapitre 5 introduit un algorithme qui supporte les pannes Byzantines et résout le problème de partition minimales en cliques en O(Δn) rounds sous le démon distribué juste dans des systèmes à identifiants uniques.Le chapitre 4 introduit un algorithme qui résout le problème du (k,k-1)-ensemble dirigeant dans les réseaux anonymes sous le démon Gouda. La construction en parallèle de tels ensembles dirigeants permet de trouver une coloration à distance K, dont on utilise les couleurs comme identifiants pour résoudre n'importe quel problème raccommodable sur des réseaux anonymes.Enfin, le chapitre 6 introduit un nouveau problème, le problème du couplage maximum minimalement coloré, qui étend des travaux antérieurs sur les couplages colorés. Ce problème est ici démontré NP-dur, et difficile à approximer sous un ratio logarithmique de la taille du graphe. Il y est également démontré qu'il W[2]-difficile en considérant le paramètre "taille de la solution", mais FPT en considérant le paramètre "taille d'un couplage maximum".

International audience; Nous proposons un algorithme, appelé SDR, qui réinitialise de manière autostabilisante et totalement distribuée un réseau anonyme, lorsque c'est nécessaire, i.e., chaque processus, détectant localement une anomalie, peut déclencher une réinitialisation. SDR est coopératif au sens où il coordonne les réinitialisations concurrentes afin de gagner en efficacité. Nous utilisons SDR pour rendre autostabilisant des algorithmes distribués. Notre approche permet de résoudre efficacement à la fois les problèmes statiques et dynamiques, comme le montrent les deux exemples d'algorithme utilisant SDR que nous proposons.

International audience; Nous formalisons des schémas d'algorithmes distribués, classiquement utilisés en autostabilisation, afin d'obtenir des résultats généraux relatifs à leur correction et leur complexité. Précisément, nous étudions une classe d'algorithmes dédiés aux réseaux munis d'un sens de direction décrivant une forêt couvrante. La définition de cette classe est simple au sens où elle est quasi-syntaxique. Tous les algorithmes de cette classe sont (1) autostabilisants et silencieux, et (2) ont un temps de stabilisation à la fois polynomial en mouvements et asymptotiquement optimal en rondes. Pour illustrer la polyvalence de notre méthode, nous passons en revue plusieurs travaux où nos résultats s'appliquent.

International audience; Cet article est un résumé étendu de (Altisen et al., Euro-Par 2016) dans lequel nous nous intéressons à des réseaux pouvant subir des changements topologiques transitoires. Nous proposons une nouvelle spécialisation de l'autostabilisation adaptée à ce type de réseau : la stabilisation progressive. Un algorithme est progressivement stabilisant sous hypothèse de (τ, ρ)-dynamicité s'il est autostabilisant et satisfait la propriété supplémentaire suivante : après au plus τ pas dynamiques vérifiant la condition ρ et se produisant à partir d'une configuration légitime, l'algorithme converge rapidement vers une configuration où une spécification plus faible est satisfaite ; puis il continue à converger progressivement vers des configurations où des spécifications de plus en plus fortes sont vérifiées, et ce, jusqu'à retrouver une configuration légitime vérifiant la spécification initiale du problème. Nous illustrons cette nouvelle propriété en proposant un algorithme progressivement stabilisant de synchronisation d'horloges.

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.

Distributed systems become increasingly wide and complex, while their usage extends to various domains (e.g., communication, home automation, monitoring, cloud computing). Thus, distributed systems are executed in diverse contexts. In this thesis, we focus on uncertain contexts, i.e., the context is not completely known a priori or is unsettled. More precisely, we consider two main kinds of uncertainty: processes that are not completely identified and the presence of faults. The absence of identification is frequent in large networks composed of massively produced and deployed devices. In addition, anonymity is often required for security and privacy. Similarly, large networks are exposed to faults (e.g, process crashes, wireless connection drop), but the service must remain available.This thesis is composed of four main contributions. First, we study the leader election problem in unidirectional rings of homonym processes, i.e., processes are identified but their ID is not necessarily unique. Then, we propose a silent self-stabilizing leader election algorithm for arbitrary connected network. This is the first algorithm under such conditions that stabilizes in a polynomial number of steps. The third contribution is a new stabilizing property designed for dynamic networks that ensures fast and gradual convergences after topological changes. We illustrate this property with a clock synchronizing algorithm. Finally, we consider the issue of concurrency in resource allocation problems. In particular, we study the level of concurrency that can be achieved in a wide class of resource allocation problem, i.e., the local resource allocation., Les systèmes distribués sont de plus en plus grands et complexes, alors que leur utilisation s'étend à de nombreux domaines (par exemple, les communications, la domotique, la surveillance, le ``cloud''). Par conséquent, les contextes d'exécution des systèmes distribués sont très divers. Dans cette thèse, nous nous focalisons sur des contextes incertains, autrement dit, le contexte n'est pas complètement connu au départ ou il est changeant. Plus précisément, nous nous focalisons sur deux principaux types d'incertitudes : une identification incomplète des processus et la présence de fautes. L'absence d'identification est fréquente dans de grands réseaux composés d'appareils produits et déployés en masse. De plus, l'anonymat est souvent une demande pour la sécurité et la confidentialité. De la même façon, les grands réseaux sont exposés aux pannes comme la panne définitive d'un processus ou une perte de connexion sans fil. Néanmoins, le service fourni doit rester disponible.Cette thèse est composée de quatre contributions principales. Premièrement, nous étudions le problème de l'élection de leader dans les anneaux unidirectionnels de processus homonymes (les processus sont identifiés mais leur ID n'est pas forcément unique). Par la suite, nous proposons un algorithme d'élection de leader silencieux et autostabilisant pour tout réseau connecté. Il s'agit du premier algorithme fonctionnant sous de telles conditions qui stabilise en un nombre polynomial de pas de calcul. La troisième contribution est une nouvelle propriété de stabilisation conçue pour les réseaux dynamiques qui garantit des convergences rapides et progressives après des changements topologiques. Nous illustrons cette propriété avec un algorithme de synchronisation d'horloges. Finalement, nous considérons la question de la concurrence dans les problèmes d'allocation de ressources. En particulier, nous étudions le niveau de concurrence qui peut être atteint dans une grande classe de problèmes d'allocation de ressources, l'allocation de ressources locales.

International audience; La composition est un outil fondamental pour élaborer des systèmes de plus en plus complexes. Dans le cadre des algorithmes distribués autostabilisants, la composition collatérale hiérarchique est un équivalent de la composition séquentielle. Nous enrichissons la bibliothèque de formalisation d'algorithmes autostabilisants PADEC de cet opérateur de composition et nous explicitons des conditions nécessaires à son utilisation. Nous démontrons la correction partielle de la composition collatérale hiérarchique et nous en prouvons la terminaison sous deux critères distincts : un critère fort pour des exécutions asynchrones et un critère plus réaliste utilisant des hypothèses d'équité faible.

It is easy to see that in a fault-free environment, it is not always true that a synchronized unison is deadlock-free or livelock-free, in the sense that all processes would execute their application code infinitely often. These kinds of problem mandates a deep study of unison.Our contribution is threefold:- understand unision and its convergence to a synchronized deadlock-free state in an arbitrary graph, and inferring new efficient protocols for general graphs;- enhance protocoles in two particular cases: synchronous networks and tree networks;- apply unison to local synchronization, and more generally to distance-d synchronization.These three axes motivate the three chapters of this study.; Il est facile de voir que même dans un univers sans panne, il n'est pas toujours vrai qu'un "unisson" synchronisé soit sans interblocage ou sans famine, au sens où tous les processus exécuteraient le code de l'application une infinité de fois. Ce type de pathologie exige une étude approfondie de l'unisson. Nos contributions s'articulent autour de trois grands axes :- comprendre l'unisson et sa convergence vers un état synchronisé sans interblocage dans un graphe quelconque, en déduire des protocoles efficaces sur le graphe général ;- améliorer les protocoles dans deux cas particuliers : les réseaux synchrones et les réseaux à topologie en arbre ;- appliquer l'unisson à la synchronisation locale, et plus généralement à la synchronisation à distance d.Ces trois axes motivent les trois parties de cette étude.

It is easy to see that in a fault-free environment, it is not always true that a synchronized unison is deadlock-free or livelock-free, in the sense that all processes would execute their application code infinitely often. These kinds of problem mandates a deep study of unison.Our contribution is threefold:- understand unision and its convergence to a synchronized deadlock-free state in an arbitrary graph, and inferring new efficient protocols for general graphs;- enhance protocoles in two particular cases: synchronous networks and tree networks;- apply unison to local synchronization, and more generally to distance-d synchronization.These three axes motivate the three chapters of this study.; Il est facile de voir que même dans un univers sans panne, il n'est pas toujours vrai qu'un "unisson" synchronisé soit sans interblocage ou sans famine, au sens où tous les processus exécuteraient le code de l'application une infinité de fois. Ce type de pathologie exige une étude approfondie de l'unisson. Nos contributions s'articulent autour de trois grands axes :- comprendre l'unisson et sa convergence vers un état synchronisé sans interblocage dans un graphe quelconque, en déduire des protocoles efficaces sur le graphe général ;- améliorer les protocoles dans deux cas particuliers : les réseaux synchrones et les réseaux à topologie en arbre ;- appliquer l'unisson à la synchronisation locale, et plus généralement à la synchronisation à distance d.Ces trois axes motivent les trois parties de cette étude.

National audience; Nous nous intéressons à la conception d'algorithmes autostabilisants pour des réseaux identifiés hautement dynamiques. Précisément, nous considérons le problème de l'élection dans trois classes de graphes dynamiques (TVG) : la classe T C B (∆) des TVG de diamètre temporel borné par ∆, la classe TCQ (∆) des TVG de diamètre temporel quasiment borné par ∆ et la classe TCR des TVG à connectivité temporelle récurrente. Nous montrons qu'en dépit des identités, dans les classes TCQ (∆) et TCR, tout algorithme autostabilisant d'élection nécessite la connaissance exacte du nombre de processus. Puis nous proposons trois algorithmes d'élection. Le premier, pour la classe TCB(∆), stabilise en au plus 3∆ rondes. Dans TCQ(∆) et TCR, le temps de stabilisation d'un algorithme autostabilisant d'élection ne peut pas être borné. Cependant, nous montrons que nos deux solutions sont spéculatives, c'est-à-dire qu'elles ont de bonnes performances dans des cas favorables ; en effet, elles stabilisent en O(∆) rondes lorsque l'on se restreint à la classe TCB(∆).

International audience; Cet article est un résumé étendu de [1] dans lequel nous présentons un algorithme distribué autostabilisant et silencieux d'élection de leader. Cet algorithme est écrit dans le modèle à états et prouvé sous l'hypothèse d'un démon distribué inéquitable, le démon le plus général du modèle. Il stabilise en Θ(n) rondes, Θ(n^3) pas et nécessite Θ(log n) bits par processus, où n est le nombre de processus. C'est à notre connaissance le premier algorithme autostabilisant asynchrone d'élection pour lequel une borne supérieure sur le temps de stabilisation en nombre de pas de calcul est prouvée.