Systèmes
Répartis
22
Classification des fautes (1)
• Des critères
– Origine de la faute
• Type de composant : ex. lignes ou sites
– Cause de la faute: bénignes ou malignes
• Défaillances temporaires ou définitives : si le composant fonctionne il
fonctionne correctement
ex. ligne transmet le msg ou non / site traite le msg ou non
• Défaillances byzantines : comportement arbitraire du composant défaillant.
Si le composant fonctionne, il ne fonctionne par correctement à l’insu des
autres composants.
ex. site répond « blanc » à certains sites et « noir » à d’autres.
23
Classification des fautes (2)
– Durée de la faute
• Définitive
• Temporaire
– Détectabilité de la faute
• Détectable localement. Réparation par le site lui-même.
• Non détectable localement. Réparation nécessite échange de messages.
24
Hiérarchie
• Sites
– Site mort-né : site n’exécute aucune instruction de son algo.
– Site en panne franche : site fonctionne correctement jusqu’à l’apparition de la
panne et cesse totalement de fonctionner.
– Site byzantin : comportement arbitraire.
25
Typologie (1)
• Panne franche
– Composant fonctionne correctement puis panne et cesse immédiatement de
fonctionner = panne permanente
• Panne franche de site
• Coupure d’une ligne => changement de topologie du réseau
• Panne transitoire
– Comportement erroné des composants pendant une certaine période.
Comportement correct ensuite.
• On peut distinguer si la panne n’apparaît qu’une fois ou plus ou moins
périodiquement
• Corruption mémoire
• Annulation d’une transaction
• Perte de messages sur une ligne
26
Typologie (2)
• Panne temporelle
– Une sortie correcte associée à une requête entrante se manifeste de façon
incohérente avec les spécifications.
• Trop tard ou jamais
• Trop tôt
• Le cas le plus fréquent est celui d'une manifestation trop-tardive.
• Ex. : Surcharge d'un processeur, Horloge trop rapide, Délai de transmission
trop long.
• Panne byzantine
– Toute panne engendrant une comportement s’écartant des spécifications
• Fautes byzantines "naturelles"
– erreur physique non détectée (sur une transmission de message,
en mémoire, sur une instruction).
– erreur logicielle amenant un non vérification des spécifications.
• Fautes byzantines "malicieuses"
– comportement visant à faire échouer le système (sabotage,virus ....).
27
Spécifications
• Spécifications pour les sites
– Si un site n’a pas atteint un état final, il finira par exécuter une autre étape de
l’algorithme
• Spécifications pour les liens de communications
– Un site j reçoit un message d’un site i au plus une fois et seulement si i a
précédemment envoyé le message à j
– Si i a envoyé un message à j et j exécute infiniment des étapes de l’algorithme
alors j finira par recevoir le message de i.
28
Algorithmes Robustes
• Robuste : Garantir la correction du comportement global du système vis à vis des
spécifications de l’algorithme
– Spécifications définies en terme d’invariants qui doivent être constamment
vérifiés
– Aucun dysfonctionnement n’est toléré pour le système
– Algorithmes robustes masquent les fautes
– Approche dite pessimiste
29
Algorithmes Robustes : exemple comportemental
• Exclusion Mutuelle
– Propriétés de sûreté et de vivacité toujours vérifiées
– Par exemple, on ne se retrouvera jamais avec une configuration où 2 sites sont
en même temps en SC
• Élection
– Un et un seul site sera élu
– Par exemple, à aucun moment il existe une configuration où simultanément
plusieurs sites décident qu’ils sont élus.
30
Algorithmes auto-stabilisants
• Finir par garantir la correction du comportement global du système vis à vis des
spécifications de l’algorithme
– Système tolère certaines périodes de dysfonctionnement
– Algorithmes ne masquent pas les fautes
– Approche dite optimiste
31
Algorithmes Auto-stabilisants: exemple comportemental
• Exclusion mutuelle
– Propriété de sûreté non vérifié pendant un intervalle de temps
– Deux sites peuvent se retrouver en SC
– MAIS au bout d’un moment le système retrouve un comportement correct
(l’algorithme retrouve de lui même un état valide)