Cohérence de calculs répartis face aux défaillances, à l'anonymat et au facteur d'échelle
Institution:
Rennes 1Disciplines:
Directors:
Abstract EN:
Nowadays, distributed systems exist in various forms; Internet, cellular phone networks, sensors networks, etc. The increasing development and diversification of electronic communicative devices promote the emergence of new networks and new related problems. This thesis first proposes a general introduction to distributed systems describing the different characteristics and problems that may be found in such systems. After this global introduction, this manuscript focuses on three specific systems. In a first chapter, we study small-worlds networks, and more precisely the routing problem in such networks: we propose, on one side, a formal analysis that allows us to obtain a precise evaluation of the cost of routing, and on the other side, a new gossip protocol that build efficient small-worlds networks in a decentralized way. In a second chapter, we focus on the exploration of graphs by mobile anonymous robots: we prove a topological bound on the number of robots that may explore a given graph, and then we describe some algorithm solving the exploration problem, depending on the vision capabilities of each robot. Finally, in a last chapter, we present results on failure detectors and consensus in anonymous asynchronous systems: after defining new detectors, we compare and rank them in a hierarchy and then we give two new failure detectors-based consensus algorithms.
Abstract FR:
Aujourd’hui les systèmes répartis existent sous de multiples formes ; le réseau Internet, le réseau de téléphonie cellulaire, des réseaux de capteurs, etc. Le développement croissant et la diversification des appareils communicants favorisent l’émergence de nouveaux réseaux et de nouveaux problèmes. Cette thèse propose tout d’abord une introduction générale sur les systèmes répartis en décrivant les différentes caractéristiques et problématiques qu’il est possible de rencontrer dans de tels systèmes. Suite à cette présentation globale, ce manuscrit décrit l’étude de trois systèmes spécifiques. Dans une première partie, nous étudions les réseaux petits-mondes et plus particulièrement la question du routage dans de tels réseaux : nous proposons d’une part une analyse fine permettant d’évaluer le coût du routage et d’autre part un nouvel algorithme épidémique construisant des réseaux petits-mondes de manière décentralisée. Dans une seconde partie, nous nous intéressons à l’exploration de graphes par des robots mobiles anonymes : nous démontrons une borne topologique sur le nombre de robots pouvant explorer un graphe, puis nous décrivons plusieurs algorithmes d’explorations dépendant des capacités de vision de chaque robot. Enfin dans une dernière partie, nous présentons des résultats sur les détecteurs de fautes et sur le problème du consensus dans des systèmes asynchrones anonymes : après une description de nouveaux détecteurs, nous démontrons qu’il existe une hiérarchie permettant de les ordonner puis nous donnons deux algorithmes les utilisant afin de résoudre le problème du consensus.