CM4 Partie1 Flashcards
Pannes franches
certains processus tombent en panne une fois pour toutes. Une fois en panne, ils n’envoient plus aucun message jusqu’à la fin de l’exécution.
Pannes temporaires
Les processus tombent en panne mais peuvent se remettre de leur pannes et reprendre leur fonctionnement normal
Cas particulier de la panne temporaire
Modèle franche est un cas particulier du modèle temporaire
Fautes d’omission
certains messages sont perdus
Cas particulier des fautes d’omission
Le modèle à panne temporaire est un cas particulier de ce modèle
Fautes Byzantines
certains processus malveillants n’exécutent pas l’algorithme d’élection de leader et cherchent à mettre des bâtons dans les roues des autres.
Cas particulier des fautes byzantines
Les autres modèles ci-dessus sont des cas particuliers du modèle Byzantin
Qui est le le modèle le plus générique et qui est le plus difficile de résoudre des problèmes distribués ?
Le modèle Byzantin
processus correct
ne tombe jamais en panne au cours de l’exécution.
processus fautif
tombe en panne à partir d’un certain moment, et ne récupère jamais.
Consensus
survient dans un système distribué dans lequel chaque processus propose initialement une valeur
Consensus But
- tous les processus se mettent d’accord sur une même valeur parmi les valeurs proposées
- Chaque processus propose une valeur primitive propose(v)
- Chaque processus décide d’1 valeur qui est commun à tous primitive decide(v)
Propriétés du consensus
- Validité: la valeur décidée doit être l’une des valeurs proposées.
- Terminaison: tous les processus corrects décident en un temps fini.
- Cohérence: deux processus corrects ne peuvent décider différemment.
- Intégrité: un processus doit décider au plus une fois.
Consensus uniforme
une version plus difficile du consensus dans laquelle la propriété d’accord s’applique à tous les processus, même fautifs
Propriété de plus de la consensus uniforme
- Cohérence uniforme : Deux processus, même fautifs, ne peuvent décider différemment.
Modèle de système distribué
- Graphe complet
- Liens de communication bidirectionnels
- n nœuds statiques
- Chaque nœud a un identifiant unique
- Messages toujours correctement reçus
- Pannes franches
Algorithme de consensus naïf - Déroulement
- Envoyer valeur proposée à tous
- Attendre de recevoir toutes les valeurs
- Décider la valeur la plus faible
Algorithme de consensus naïf - Fonctionne quand?
Fonctionne uniquement en l’absence de pannes
Modèles temporels Système synchrone
- Borne ∆ sur le temps de transmission des processus.
- Borne Φ sur la vitesse relative des processus
Modèles temporels Système synchrone - permet quoi ?
Permet une détection parfaite des fautes.
Modèles temporels Système asynchrone
- Pas de borne sur les temps de transmission.
- Pas de borne sur la vitesse relative des processus.
Qu’est ce qu’on ne peut pas faire dans un Modèles temporels Système asynchrone?
On ne peut pas faire la différence entre un processus lent et un processus en panne
Impossibilité de Fischer, Lynch et Paterson (FLP 85)
Il est impossible de résoudre le consensus de façon déterministe dans un système asynchrone en présence de crashs.
Comment contourner le FLP?
- Changer le problème : problème du k-accord
- Changer le modèle : modèle partiellement synchrone
- Abstraction du modèle : détecteurs de fautes
- Résoudre un consensus imparfait
problème du k-accord
- généralisation du consensus dans lequel plusieurs valeurs différentes peuvent être décidées.
- Le paramètre k détermine le nombre maximal de valeurs qui peuvent être décidées.
- la propriété de la cohérence du consensus change
modèle partiellement synchrone
une famille de modèles de systèmes qui sont plus réalistes que le modèle synchrone, tout en permettant la résolution du consensus.
variantes de modèles partiellement synchrones
- dans certains modèles, les bornes ∆ et Φ sont connues mais ne s’appliquent qu’après un certain temps ;
- dans d’autres modèles, les bornes ∆ et Φ sont inconnues, mais s’appliquent dès le début de l’exécution.
Détecteurs de fautes
des outils qui fournissent à chaque processus des informations sur les fautes des autres processus dans le système
Quelle est la forme des informations fournis par les détecteurs de fautes?
- prend la forme d’une liste de processus «de confiance».
- Les processus sur cette liste sont présumés corrects, tandis que les processus absents de la liste sont présumés
en panne
Les infos fournies par le détecteur peuvent ne pas être fiables?
Oui . Un processus peut faire confiance à un processus
eu panne, ou bien suspecter un processus correct (on parle de fausse suspicion).
Dans quel cas le retard dans la détection de fautes est inévitable?
Il est inévitable quel que soit le modèle
Dans quel cas le fausses suspicions sont inévitable ou évitable?
- Inévitable en asynchrone
- Évitable en synchrone
- Temporairement inévitable en partiellement synchrone
Propriétés des détecteurs de fautes
- complétude : exige que les corrects détectent les fautifs
- justesse : interdit les fausses suspicions
C’est quoi la complétude forte ?
- Complétude forte: après un certain temps,tous les fautifs sont suspectés par tous les corrects.
C’est quoi la complétude faible ?
- Complétude faible: après un certain temps, tous les fautifs sont suspectés par un correct.
C’est quoi la justesse forte?
- les corrects ne sont jamais suspectés.
C’est quoi la justesse faible?
- un correct n’est jamais suspecté.
C’est quoi la justesse finalement forte?
- après un certain temps, les corrects ne sont jamais suspectés
C’est quoi la justesse finalement faible?
- après un certain temps, un correct n’est jamais suspecté.
Quels sont les détecteurs les plus importants?
- le détecteur P (aussi appelé le détecteur parfait), qui n’autorise aucune fausse suspicion ;
- le détecteur S (prononcé «diamant S»), qui ne fournit de garanties qu’à terme.
Quand dit-on qu’un détecteur est plus fort qu’un autre?
un détecteur D1 est plus fort qu’un détecteur D2, si et seulement si il existe un algorithme qui permet de construire D2 en s’appuyant uniquement sur les informations fournies par D1
Comment est la relation de notion de forces ?
cette relation est transitive
