Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Algo distribuée > CM4 Partie1 > Flashcards

CM4 Partie1 Flashcards

1
Q

Pannes franches

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Pannes temporaires

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Cas particulier de la panne temporaire

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Fautes d’omission

A

certains messages sont perdus

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Cas particulier des fautes d’omission

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Fautes Byzantines

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Cas particulier des fautes byzantines

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

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 ?

A

Le modèle Byzantin

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

processus correct

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

processus fautif

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Consensus

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Consensus But

A
  • 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)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Propriétés du consensus

A
  • 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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Consensus uniforme

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Propriété de plus de la consensus uniforme

A
  • Cohérence uniforme : Deux processus, même fautifs, ne peuvent décider différemment.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Modèle de système distribué

A
  • Graphe complet
  • Liens de communication bidirectionnels
  • n nœuds statiques
  • Chaque nœud a un identifiant unique
  • Messages toujours correctement reçus
  • Pannes franches
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Algorithme de consensus naïf - Déroulement

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

Algorithme de consensus naïf - Fonctionne quand?

A

Fonctionne uniquement en l’absence de pannes

19
Q

Modèles temporels Système synchrone

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

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

A

Permet une détection parfaite des fautes.

21
Q

Modèles temporels Système asynchrone

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

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

A

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

23
Q

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

A

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

24
Q

Comment contourner le FLP?

A
  • 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
25
Q

problème du k-accord

A
  • 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
26
Q

modèle partiellement synchrone

A

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.

27
Q

variantes de modèles partiellement synchrones

A
  • 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.
28
Q

Détecteurs de fautes

A

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

29
Q

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

A
  • 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
30
Q

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

A

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

31
Q

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

A

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

32
Q

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

A
  • Inévitable en asynchrone
  • Évitable en synchrone
  • Temporairement inévitable en partiellement synchrone
33
Q

Propriétés des détecteurs de fautes

A
  • complétude : exige que les corrects détectent les fautifs
  • justesse : interdit les fausses suspicions
34
Q

C’est quoi la complétude forte ?

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

C’est quoi la complétude faible ?

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

C’est quoi la justesse forte?

A
  • les corrects ne sont jamais suspectés.
37
Q

C’est quoi la justesse faible?

A
  • un correct n’est jamais suspecté.
38
Q

C’est quoi la justesse finalement forte?

A
  • après un certain temps, les corrects ne sont jamais suspectés
39
Q

C’est quoi la justesse finalement faible?

A
  • après un certain temps, un correct n’est jamais suspecté.
40
Q

Quels sont les détecteurs les plus importants?

A
  • 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.
41
Q

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

A

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

42
Q

Comment est la relation de notion de forces ?

A

cette relation est transitive

Algo distribuée (11 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions