CM4 Partie1

Question 1

Pannes franches

Answer 1

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.

Question 2

Pannes temporaires

Answer 2

Les processus tombent en panne mais peuvent se remettre de leur pannes et reprendre leur fonctionnement normal

Question 3

Cas particulier de la panne temporaire

Answer 3

Modèle franche est un cas particulier du modèle temporaire

Question 4

Fautes d’omission

Answer 4

certains messages sont perdus

Question 5

Cas particulier des fautes d’omission

Answer 5

Le modèle à panne temporaire est un cas particulier de ce modèle

Question 6

Fautes Byzantines

Answer 6

certains processus malveillants n’exécutent pas l’algorithme d’élection de leader et cherchent à mettre des bâtons dans les roues des autres.

Question 7

Cas particulier des fautes byzantines

Answer 7

Les autres modèles ci-dessus sont des cas particuliers du modèle Byzantin

Question 8

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 ?

Answer 8

Le modèle Byzantin

Question 9

processus correct

Answer 9

ne tombe jamais en panne au cours de l’exécution.

Question 10

processus fautif

Answer 10

tombe en panne à partir d’un certain moment, et ne récupère jamais.

Question 11

Consensus

Answer 11

survient dans un système distribué dans lequel chaque processus propose initialement une valeur

Question 12

Consensus But

Answer 12

• 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)

Question 13

Propriétés du consensus

Answer 13

• 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.

Question 14

Consensus uniforme

Answer 14

une version plus difficile du consensus dans laquelle la propriété d’accord s’applique à tous les processus, même fautifs

Question 15

Propriété de plus de la consensus uniforme

Answer 15

• Cohérence uniforme : Deux processus, même fautifs, ne peuvent décider différemment.

Question 16

Modèle de système distribué

Answer 16

• Graphe complet
• Liens de communication bidirectionnels
• n nœuds statiques
• Chaque nœud a un identifiant unique
• Messages toujours correctement reçus
• Pannes franches

Question 17

Algorithme de consensus naïf - Déroulement

Answer 17

• Envoyer valeur proposée à tous
• Attendre de recevoir toutes les valeurs
• Décider la valeur la plus faible

Question 18

Algorithme de consensus naïf - Fonctionne quand?

Answer 18

Fonctionne uniquement en l’absence de pannes

Question 19

Modèles temporels Système synchrone

Answer 19

• Borne ∆ sur le temps de transmission des processus.
• Borne Φ sur la vitesse relative des processus

Question 20

Modèles temporels Système synchrone - permet quoi ?

Answer 20

Permet une détection parfaite des fautes.

Question 21

Modèles temporels Système asynchrone

Answer 21

• Pas de borne sur les temps de transmission.
• Pas de borne sur la vitesse relative des processus.

Question 22

Qu’est ce qu’on ne peut pas faire dans un Modèles temporels Système asynchrone?

Answer 22

On ne peut pas faire la différence entre un processus lent et un processus en panne

Question 23

Impossibilité de Fischer, Lynch et Paterson (FLP 85)

Answer 23

Il est impossible de résoudre le consensus de façon déterministe dans un système asynchrone en présence de crashs.

Question 24

Comment contourner le FLP?

Answer 24

• 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

Question 25

problème du k-accord

Answer 25

* 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

Question 26

modèle partiellement synchrone

Answer 26

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.

Question 27

variantes de modèles partiellement synchrones

Answer 27

* 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.

Question 28

Détecteurs de fautes

Answer 28

des outils qui fournissent à chaque processus des informations sur les fautes des autres processus dans le système

Question 29

Quelle est la forme des informations fournis par les détecteurs de fautes?

Answer 29

* 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

Question 30

Les infos fournies par le détecteur peuvent ne pas être fiables?

Answer 30

Oui . Un processus peut faire confiance à un processus eu panne, ou bien suspecter un processus correct (on parle de **fausse suspicion**).

Question 31

Dans quel cas le retard dans la détection de fautes est inévitable?

Answer 31

Il est inévitable quel que soit le modèle

Question 32

Dans quel cas le fausses suspicions sont inévitable ou évitable?

Answer 32

* Inévitable en asynchrone * Évitable en synchrone * Temporairement inévitable en partiellement synchrone

Question 33

Propriétés des détecteurs de fautes

Answer 33

* **complétude** : exige que les corrects détectent les fautifs * **justesse** : interdit les fausses suspicions

Question 34

C'est quoi la complétude forte ?

Answer 34

* Complétude **forte**: après un certain temps,**tous les fautifs** sont suspectés par **tous les corrects**.

Question 35

C'est quoi la complétude faible ?

Answer 35

* Complétude **faible**: après un certain temps, **tous les fautifs** sont suspectés par **un correct**.

Question 36

C'est quoi la justesse forte?

Answer 36

* **les corrects** ne sont jamais suspectés.

Question 37

C'est quoi la justesse faible?

Answer 37

* **un correct** n’est jamais suspecté.

Question 38

C'est quoi la justesse finalement forte?

Answer 38

* **après un certain temps, les corrects** ne sont jamais suspectés

Question 39

C'est quoi la justesse finalement faible?

Answer 39

* **après un certain temps, un correct** n’est jamais suspecté.

Question 40

Quels sont les détecteurs les plus importants?

Answer 40

* **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.

Question 41

Quand dit-on qu'un détecteur est plus fort qu'un autre?

Answer 41

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

Question 42

Comment est la relation de notion de forces ?

Answer 42

cette relation est **transitive**