Derrière le consensus (coordination faiblement contrainte dans les systèmes distribués asynchrones)

L'informatique moderne est distribuée. La distribution du calcul résulte parfois d'un besoin applicatif lorsque l'objectif est de connecter des ordinateurs distants. Parfois, elle naît du besoin de tolérer des défaillances. En effet, pour éviter qu'une application ne soit à la merci de la défaillance d'une machine, le calcul est dupliqué sur plusieurs machines. Au coeur de tout calcul réparti repose une forme de coordination. Le fait même que des ordinateurs aient une tâche commune implique un besoin de se concerter avant d'accomplir certaines tâches. Nous étudions les problèmes de coordination dans le modèle asynchrone, sans hypothèses sur des bornes de vitesse d'exécution des processeurs ou de transmission des messages. Les processus peuvent défaillir à n'importe quel moment. Le degré de coordination qui peut être atteint en fonction du degré d'incertitude du système est la question principale de cette thèse. Trois formes de coordination sont considérées : l'accord ensembliste, le renommage et le consensus simultané. Dans un premier temps, nous proposons différentes réductions algorithmiques entre ces problèmes, afin de prouver dans quelle condition une solution à l'un de ces problèmes permet d'obtenir une solution à un autre problème. Nous étudions ensuite des hypothèses nécessaires et suffisantes sur la détection de défaillances permettant de résoudre les problèmes d'accord. Le formalisme utilisé ici est celui des détecteurs de défaillances. Enfin, nous proposons un autre point de vue sur les détecteur de défaillances. Nous caractérisons la puissance de calcul amenée par ces détecteurs par une restriction des exécutions du modèle itéré de E. Gafni.In an asynchronous distributed system, independent processes run at varying speeds and may even crash; they communicate through unsynchronized primitives, like sending and receiving messages. To perform shared computation, processes need to coordinate their actions. This is theoretically modeled as solving a coordination task, where processes start with some inputs and have to output values satisfying certain conditions. A fundamental task is consensus, from which it is possible to solve any other coordination task. However, this task is not solvable in asynchronous failures prone environments. We study sub-consensus tasks, i.e., coordination tasks that are weaker than consensus. In particular, we focus on renaming which requires processes to rename in a tighter name space, k-set-consensus which extends consensus by allowing processes to decide on a small number (k) of values and the committee-decision. We first explore, through algorithmic reductions, the relationships between these sub-tasks. The second part deals with the use of failure detector to solve set agreement. A failure detector is a distributed oracle giving indications about the correctness of processes. We determine the relative computational power provided by various families of failure detectors. The last part looks as failure detector as mechanisms to restrict the possible executions rather than oracle. Specifically, for each failure detector fd presented in the thesis, we define a restriction of the iterated immediate snapshot model of Gafni that has exactly the same computational power (in the sense of ability to solve coordination tasks) as the ordinary model enhanced with fd.RENNES1-BU Sciences Philo (352382102) / SudocSudocFranceF