CM3 Partie1

Question 1

Quel est l’objectif de l’élection de leader?

Answer 1

Choisir les nœuds qui peuvent avoir des rôles particuliers : source, racine

Question 2

Comment doit être l’élection de leader?

Answer 2

• Sure : Le leader doit être unique et un nœud a été élu
• Rapide : Le choix doit se faire en un temps fini

Question 3

Que permet de faire l’élection de leader dans un système distribué?

Answer 3

de rompre la symétrie dans un système
distribué

Question 4

Les applications de l’élection de leader

Answer 4

• Orchestration dans un système distribué
• Faire face à des défaillances
• Récupérer de l’information sur le graphe (Détecter la terminaison d’un algo/Déterminer le nombre de nœuds dans le réseau)

Question 5

Dans quel contexte est-il impossible de faire un algo déterministe d’élection de leader et pourquoi ?

Answer 5

• Dans les systèmes distribués anonymes et uniformes
• Parce que on n’atteint jamais un état asymétrique dans lequel on pourrait choisir un leader

Question 6

C’est quoi un système uniforme ?

Answer 6

• Les nœuds n’ont pas d’ID
• Impossible de différencier les nœuds

Question 7

Comment contourner ce résultat d’impossibilité d’élection de leader dans un système anonyme?

Answer 7

• En utilisant des identifiants uniques sur les nœuds
• En utilisant des algos probabilistes

Question 8

Algorithme de Changs-Roberts
Type d’anneau, type d’algo

Answer 8

• Utilisé dans un anneau unidirectionnel
• Algorithme déterministe

Question 9

Les hypothèses de l’algo de Changs-Roberts

Answer 9

• Chaque nœud a un identifiant unique et sait que les identifiants sont uniques
• Chaque nœud connaît son voisin
• Le nombre de nœuds dans le système est inconnu de chaque nœud

Question 10

La pire et la meilleure scénario de Changs-Roberts

Answer 10

• Pire scénario: tous les nœuds se portent candidats
• Meilleure scénario: le nœud avec le plus grand ID se porte candidat

Question 11

Comment compléter l’algo de Changs Roberts?

Answer 11

Avec la diffusion du message Lead à tous les nœuds de l’anneau :
* permet aux nœuds de connaitre le leader
* de savoir que l’algo est terminé

Question 12

Complexité de l’algo de Changs-Roberts

Answer 12

• Meilleure scénario : 2n messages
• Pire scénario: O(n au carré)

Question 13

Algorithme d’Itai-Rodeh
Type d’anneau, type d’algo

Answer 13

• Utilisé dans un anneau unidirectionnel anonyme
• Algorithme probabiliste

Question 14

Les hypothèses de l’algo d’Itai-Rodeh

Answer 14

• Nœuds n’ont plus forcément un identifiant unique
• Nœuds connaissent le nombre total de nœuds n
• Chaque nœud connaît son voisin
• Communications FIFO

Question 15

Les messages de l’algo d’Itai-Rodeh contiennent quoi ?

Answer 15

• Id du nœud
• Numéro de phase
• Nombre de sauts du message
• Un booléen initialisé à vrai qui va dire si l’ID est unique ou pas

Question 16

Quand est ce que l’algo d’Itai-Rodeh ne se termine pas?

Answer 16

Quand les nœuds candidats choisissent le même ID à chaque fois

Question 17

Algorithme d’Hirschberg-Sinclair
Type d’anneau

Answer 17

Utilisé dans un anneau bidirectionnel

Question 18

Les hypothèses de l’algo d’Hirschberg-Sinclair

Answer 18

• Chaque nœud a un voisin à droite et à voisin à gauche auxquels il peut envoyer des messages
• Chaque nœud peut recevoir des messages de ses 2 voisins
• Nœuds ont un identifiant unique

Question 19

Qui ont le droit de participer à la vague r+1 dans l’algo d’Hirschberg-Sinclair ?

Answer 19

À la vague r, un nœud est gagnant s’il a le plus grand identifiant parmi les 2^r voisins à sa droite et les 2^r voisins à sa gauche

Question 20

A quelle distance sont deux nœuds qui restent en compétition à la vague r?

Answer 20

les deux nœuds sont à une distance > 2^r

Question 21

Quelle est l’algo la plus efficace entre Changs Roberts et Hirschberg-Sinclair ?

Answer 21

C’est l’algo d’Hirschberg-Sinclair