Tolérance aux défaillances dans les réseaux dynamiques
Institution:
Paris 7Disciplines:
Directors:
Abstract EN:
We study how some fault-tolerant algorithms for classical Systems can be extended to t}e used in larger scale networks. In the first part of this thesis we address the problems of reliable broadcast and consensus in sensor networks communicating with radio-broadcast. Communication is prone to collision when several sensors broadcast simultaneously. Moreover sensors may crash and stop sending. In this framework, reliable broadcast and consensus are not possible to solve. Sensors are equipped with collision detectors. We propose some specifications of collision detectors that enable us to achieve reliable broadcast, consensus and we give some algorithms for this. In the second part we consider a dynamic network of processes communicating by sending messages. The network is dynamic in the sense that the processes are created dynamically and each process does not know either the number or the set of created processes, but it has a unique identity. Created processes are prone to failure. We study three classical problems of fault-tolerance in the case where the set of processes is unknown. The three problems are: the consensus problem, the implementation of atomic registers and the eventual leader election. For this we consider different models in respect of their degree of synchrony (asynchronous, partially synchronous, synchronous), and we prove how to solve these problems in every considered models.
Abstract FR:
On étudie comment certaines solutions de l'algorithmique tolérante aux défaillances pour des systèmes à petite échelle peuvent s'étendre à des réseaux à plus grande échelle. Dans la première partie on considère des réseaux de capteurs communiquant en rondes synchrones par radiodiffusion. Le nombre de capteurs n'est pas connu et les capteurs peuvent être anonymes, de plus certains capteurs peuvent tomber en panne définitive et cesser d'émettre. En présence de collisions de messages, des problèmes comme le consensus ne peuvent être résolus. Aussi on suppose que les capteurs sont équipés de détecteurs de collision qui donnent des informations (non nécessairement fiables) sur les collisions. En considérant un modèle de communication rudimentaire sans message, on montre que des détecteurs de collision très simples permettent de résoudre le problème du consensus, de la diffusion fiable et de calculer le maximum des valeurs proposées à la diffusion. Dans la seconde partie on considère un réseau dynamique de processus communiquant par passage de messages. Le réseau est dynamique dans le sens où les processus sont créés dynamiquement et que les processus ne connaissent ni le nombre ni l'ensemble des processus créés mais ont des identités uniques. On suppose que les processus créés peuvent tomber en panne crash. On y étudie trois problèmes classiques de la tolérance aux défaillances: le problème du consensus, l'implantation de registres atomiques et l'élection ultime de leader. Pour cela on considère différents modèles suivant leur degré de synchronie (de totalement asynchrones, partiellement synchrone, synchrone), et on montre comment résoudre ces problèmes.