CM4 Partie2

Question 1

Le détecteur de leader Ω

Answer 1

Indique un seul processus correct.
À terme, le même pour tout le monde.
Les processus ne savent pas quand l’état stable est atteint !.
Ω est équivalent à S.

Question 2

Algorithme de consensus avec détecteur P- Hypothèses

Answer 2

Hypothèse : détecteur P
Rondes asynchrones
1 leader différent à chaque ronde
id leader = numéro ronde

Question 3

Algorithme de consensus avec détecteur P- Déroulement

Answer 3

À chaque ronde :
Leader décide sa valeur et la diffuse à tous
Chaque autre processus attend :
Soit de recevoir la valeur du leader (puis adopte la valeur du leader)
Soit le crash du leader
Tous les corrects décident en n rondes.

Question 4

Un autre algorithme de consensus avec détecteur P Hypothèse

Answer 4

détecteur P

Question 5

Un autre algorithme de consensus avec détecteur P- f c’est quoi et que maintient les processus

Answer 5

f = nombre maximum de fautes tolérées
Chaque processus maintient un vecteur contenant les valeurs proposées

Question 6

Un autre algorithme de consensus avec détecteur P- déroulement

Answer 6

f + 1 rondes :
Chaque processus diffuse son vecteur
Attend la réception des vecteurs de tous les processus non suspectés
Après f + 1 rondes :
Chaque processus décide la première valeur non vide de son vecteur
Tous les corrects décident en f + 1 rondes.

Question 7

Algorithme du coordinateur tournant - Hypothèses :

Answer 7

Majorité de corrects
Détecteur S

Question 8

Algorithme du coordinateur tournant - Comment est choisi le coordinateur

Answer 8

1 coordinateur (leader) différent à chaque ronde
id coordinateur = numéro ronde mod n
Le coordinateur impose sa valeur, qui est choisie si il n’est pas suspecté.

Question 9

Phase 1 du coordinateur tournant

Answer 9

Phase 1: estimation
Chaque processus envoie au coordinateur sa valeur courante

Question 10

Phase 2 du coordinateur tournant

Answer 10

Phase 2: proposition
Le coordinateur attend une majorité de valeurs.
Il choisit la plus à jour, puis la diffuse.

Question 11

Phase 3 du coordinateur tournant

Answer 11

Phase 3: ack
Pour chaque correct:
Si réception de la valeur, renvoyer ack au coordinateur.
Si le coordinateur est soupçonné, renvoyer nack.

Question 12

Phase 4 du coordinateur tournant

Answer 12

Phase 4: décision
Le coordinateur attend une majorité de réponses (ack ou nack).
Si majorité de ack, décision puis diffusion de la valeur.
Les autres processus décident à la réception.
Sinon, on passe à la ronde suivante.

Question 13

Consensus probabiliste - Caractéristiques

Answer 13

Déterministe : validité, cohérence, intégrité
Probabiliste : terminaison

Question 14

Limite de l’approche à coordinateur tournant

Answer 14

Nécessite des canaux fiable (peu réaliste)
* Impact de la perte de message : Blocage

Question 15

Avantage de Paxos à Coordinateur tournant

Answer 15

Eviter d’être bloqué dans une ronde
– Changer de ronde sur l’expiration d’un temporisateur
– Changer de ronde si d’autres nœuds ont changé
* Maintenir le principe du leader pour connaître les
valeurs courantes (majorité

Question 16

Paxos- Hypothèses

Answer 16

Communication
– Asynchrone
– Pas d’altération de messages
– Possibilité de pertes
* Processus
– Nombre fixe
– Fautes franches avec possibilité de reprise (crashrecovery). Chaque processus possède un état persistant