Réécriture de Graphes avec Défaillances et Algorithmes Distribués

Abstract

En algorithmique distribuée, chaque système peut être représenté par un graphe étiqueté, où les sommets correspondent aux différents terminaux, les arêtes aux liens de communication et les étiquettes associées aux sommets codent les états des processeurs. Dans un mécanisme de ré étiquetage local, un algorithme distribué est décrit par un système de règles de transition locale où la nouvelle étiquette d’un sommet est fonction de son étiquette précédente et de celles de ses voisins. Dans le cadre de ce mémoire, nous étudions la réalisabilité et non-réalisabilité des tâches distribuées. Nous illustrons notre méthode en nous intéressant en particulier à certains problèmes spécifiques aux systèmes distribués (élection d’un nœud, énumération de graphes, problème de consensus et découverte de topologie dans les réseaux Ad Hoc). Dans tous ces cas, nous caractérisons ce que n’est pas réalisable par calcul distribué en fonction de la topologie du graphe sous-jacent et de la connaissance structurelle de ce graphe. Les différents cas d’impossibilité de calcul d’une manière distribuée sont dus aux « similarités » de familles de réseaux. Ces « similarités » sont décrites à l’aide de morphismes de graphes particuliers : les revêtements et les quasi-revêtements. Les preuves d’impossibilité emploient des techniques de simulation à base de ces morphismes.