next up previous contents
suivant: Élection ultime de leader monter: Travaux récents: algorithmique distribuée précédent: Détecteurs de défaillances et   Table des matières

Détecteur minimal

Un avantage des détecteurs de défaillances est le fait que l'on peut les comparer: un détecteur est plus faible qu'un autre si il existe un algorithme distribué permettant de réaliser ce dernier à partir du premier. On peut alors déterminer quelle est le détecteur de défaillances minimal pour résoudre un problème donné, on détermine alors quelle est la connaissance minimale sur les défaillances pour résoudre ce problème.

Ce détecteur minimal permet ensuite de définir les conditions minimales que doit assurer le système pour résoudre un problème donné. De cette façon, on obtient les conditions minimales sur le système sous-jacent pour résoudre ce problème.

Dans [21], on détermine quel est le plus faible détecteur de défaillances pour résoudre le problème classique de l'exclusion mutuelle en présence de défaillances. Dans [10], nous déterminons le plus faible détecteur de défaillances pour résoudre le consensus dans le cas où une majorité de processus peuvent tomber en pannes. Il s'agissait d'un problème ouvert depuis près de 10 ans.

D'autre part dans [8], nous montrons, dans un certain sens, que tous les détecteurs de défaillances permettant de résoudre le consensus pour un nombre quelconque de pannes sont équivalents au détecteur parfait.

Déterminer le détecteur de défaillances minimal permet aussi d'obtenir des résultats généraux concernant les modèles. Ainsi, de façon classique, on considère deux grandes familles de modèles pour les systèmes distribués asynchrone: les modèles à mémoire partagées dans lesquels l'échange d'information entre processeurs se fait par l'intermédiaire de registres atomiques et les modèles à échange de messages où la seule interaction entre processus a lieu par une communication asynchrone. Déterminer quel est le plus faible détecteur de défaillances pour implémenter des registres atomiques [29] permet de faire le lien entre ces deux modèles. Dans le modèle à mémoire partagée, on peut spécifier des objets wait-free comme par exemple le test-and-set ou le compare-and-swap et s'intéresser à leur puissance relative. Une mesure classique pour définir la puissance des ces objets est entre combien de participants de tels objets permettent de réaliser le consensus. On obtient ainsi une hiérarchie stricte de ces objets. Dans les modèles à échange de messages la situation est différente: cette hiérarchie se réduit à deux éléments [29]. D'un point de vue pratique cela signifie qu'implémenter dans de tels systèmes n'importe quel objet non trivial est aussi difficile qu'implémenter le consensus. Ces résultats s'obtiennent grâce à la minimalité des détecteurs de défaillances.




next up previous contents
suivant: Élection ultime de leader monter: Travaux récents: algorithmique distribuée précédent: Détecteurs de défaillances et   Table des matières
2004-04-07