Olivier Lemer
Panne dont on ne reviendra jamais
A
∞
B
∞
On dit qu'un processus est correct en terme de panne permanente
quand il ne tombera jamais en panne permanente.
L'aspect "correct" est une caractéristique théorique.
Elle servira à analyser les algorithmes du cours.
(e.g. "cet algorithme fonctionne ssi tous les processus sont corrects en terme de panne permanente",
équivalent à dire "cet algorithme fonctionne ssi aucun processus ne tombe en panne.")
Elle n'a aucun sens dans la vraie vie.
(Impossible de savoir si un processus tombera un jour en panne ou non)
Panne dont on peut revenir, parfois en ayant perdu des informations ("amnésie").
On dit qu'un processus est correct en terme de panne récupérable
quand il existe un instant T après lequel il ne tombera plus en panne.
A
∞
Donc, un processus qui tombe constamment en panne, ou qui ne revient jamais d'une panne n'est pas correct.
Un processus qui revient d'une panne en est conscient.
B
∞
T
a.k.a. byzantine
Panne suite à laquelle tout est possible...
Peut être due à un bug, ou bien à une corruption par un agent malicieux.
A
∞
On dit qu'un processus est correct en terme de panne arbitraire
quand il suivra toujours l'algorithme attendu.
B
∞
Évidemment, le type de panne le plus couteux à supporter.
Panne d'omission
Lorsqu'un message devant être envoyé ne l'est pas.
Panne d'eavesdropping
Lorsqu'un message peut être lu par une entité extérieure au système.
"Surveille <id>"
"Panne de <id> détectée"
"Arrête de surveiller <id>"
Propriétés
p est détecté par un quelconque processus, alors p est en panne.Supposons pour l'instant des pannes permanentes uniquement.
Détecteur de pannes parfait
T sur la durée de transit de tout message.On parle de système distribué "synchrone".
B
A
"Surveille B"
PING
PONG
PING
PONG
PONG
PING
Périodiquement, le surveillant
envoie un ping, et
lance un timer de 2T.
Le surveillé
répond à ping par pong.
À la fin du timer,
Si le pong a été reçu,
Un nouveau ping est envoyé
Un nouveau timer est lancé
B
A
"Surveille B"
PING
Périodiquement, le surveillant
envoie un ping, et
lance un timer de 2T.
"Panne de B détectée"
Le surveillé
répond à ping par pong.
À la fin du timer,
Si le pong a été reçu,
Un nouveau ping est envoyé
Un nouveau timer est lancé
Sinon,
Une panne est signalée
Est-ce que ça vérifie
Complétude ?
Précision ?
Oui, un processus en panne permanente ne répondra plus aux pings, et après 2T, cette panne sera découverte.
Oui, puisqu'un message ne prend jamais plus de T unités de temps pour transiter, je dois avoir reçu un pong après 2T si le processus est correct.
Problème ?
La supposition d'un système synchrone est irréaliste. Les vrais réseaux ne nous donnent pas de garantie sur la durée de transit d'un message.
"Un jour, tout processus en panne sera détecté par tout processus correct."
"Si un processus p est détecté par un quelconque processus, alors p est en panne."
"Surveille <id>"
"Panne de <id> suspectée"
"Arrête de surveiller <id>"
Propriétés
"Suspicion de <id> annulée"
Détecteur de pannes parfait un jour
On parlera ici de système distribué "partiellement synchrone".
T inconnue sur la durée de transit de tout message.B
A
"Surveille B"
PING
"Panne de B suspectée"
PONG
"Suspicion de B annulée"
Initialement,
envoie un ping, et
lance un timer de durée 𝚫
Le surveillé
répond à ping par pong.
À la fin du timer,
Si le pong n'a pas été reçu,
𝚫 est incrémenté d'une constante
lance un timer de durée 𝚫
Envoie un ping, et
Une panne est suspectée
Si un pong est reçu d'un suspecté
La suspicion est annulée.
PING
PING
PONG
PONG
Est-ce que ça vérifie
Complétude ?
Précision un jour ?
Oui, un processus en panne permanente ne répondra plus aux pings, et après 𝚫, cette panne sera découverte.
Oui, un processus correct (en terme de panne permanente comme récupérable) répondra aux pings en un temps fini ; quand 𝚫 sera assez grand, plus de panne ne sera suspectée : tout processus sera soit "en panne" et suspecté pour toujours, ou "correct" et plus jamais suspecté.
Était-il nécessaire d'avoir un timeout dynamique ?
Oui, sinon on risquerait de constamment suspecter un processus qui est simplement lent mais bien correct.
"Un jour, tout processus en panne permanente sera suspecté par tout processus correct."
"Un jour, aucun processus correct ne sera suspecté par un processus correct."