Détecteurs de défaillances et modèle de calcul

Un autre aspect de mes travaux porte sur les problèmes d'efficacité et de comparaison entre les modèles de calcul.

Il est assez naturel d'essayer de minimiser l'usage des détecteurs de défaillances et plus généralement l'usage des oracles nécessaires à la réalisation du consensus. C'est le sens des algorithmes ``économes'' pour la diffusion générique [5] et de l'algorithme de multi-diffusion authentique [4] que nous avons proposés.

Concernant les détecteurs de défaillances, dans [2] et plus récemment dans [9], nous avons donné des bornes inférieures pour atteindre le consensus avec divers détecteurs de défaillances. Le résultat le plus étonnant est que le nombre de pannes n'intervient pour le détecteur de défaillances $\cal S$ (il s'agit d'un détecteur de défaillances assurant que tous les processus en pannes finiront par être suspectés d'être en panne et qu'au moins un processus correct n'est jamais suspecté).

Le résultat de [25] montre qu'avec des détecteurs de défaillances parfaits (un détecteur parfait fournit des informations exactes sur les défaillances) on obtient la même efficacité qu'avec un système synchrone même dans le cas de l'arrêt au plus tôt.

Dans [14], à partir de différents modèles de calcul on montre qu'on peut par une transformation automatique augmenter la tolérance aux défaillances et qu'on peut alors transformer tout algorithme défini dans un environnement sans défaillances en un algorithme efficace pour un environnement avec défaillances. Dans cette transformation les résultats des calculs sont obtenus avec décalage constant pour le temps par rapport à l'exécution de l'algorithme sans pannes.