CM3 Partie2

Question 1

Algorithme de Dolev-Klawe-Robeh
Type d’anneau

Answer 1

Utilisé dans un anneau unidirectionnel

Question 2

Les hypothèses de l’algorithme de Dolev-Klawe-Robeh

Answer 2

• Chaque nœud a un voisin à gauche
• Nœuds ont un identifiant unique et savent que les identifiants sont uniques

Question 3

Élection dans une topologie quelconque Algo 1-Hypothèse?

Answer 3

• Système connexe
• Chaque nœud connaît le nombre de nœuds dans le système
• Chaque nœud connaît son identifiant unique compris entre [1 ; n]

Question 4

Élection dans une topologie quelconque Algo 1-Qui est élu?

Answer 4

• Le leader est celui qui a l’identité la plus grande (ou la plus petite)
• Il est déterminé par chaque nœud sans échange de message

Question 5

Élection dans une topologie quelconque Algo 1-Quelle est sa force?

Answer 5

Sa force est le fait de savoir au départ que les ID de tous les nœuds sont connus

Question 6

Élection dans une topologie quelconque Algo 2-Hypothèses

Answer 6

• Système connexe
• Chaque nœud connaît le nombre de nœuds dans le système
• Chaque nœud connaît son identifiant unique

Question 7

Élection dans une topologie quelconque Algo 2-Qui est élu?

Answer 7

• Lorsque chaque nœud a reçu toutes les identités du système, le leader est celui qui a l’identité la plus grande (ou la plus petite)

Question 8

Élection dans une topologie quelconque Algo 2-Complexité

Answer 8

O(nm) messages

Question 9

Élection dans une topologie quelconque Algo 3-Type d’algo

Answer 9

Algorithme faiblement synchrone

Question 10

Élection dans une topologie quelconque Algo 3-Hypothèses

Answer 10

• Système connexe
• Chaque nœud connaît le diamètre du graphe sous-jacent
• Chaque nœud connaît son identifiant unique

Question 11

Élection dans une topologie quelconque Algo 3-Complexité

Answer 11

O(Dm) messages

Question 12

Ensemble indépendant

Answer 12

Sous-ensemble de sommets du graphe tel que 2 sommets
quelconques de ce sous-ensemble ne sont pas voisins dans le graphe

Question 13

Ensemble indépendant maximal

Answer 13

Un ensemble indépendant est maximal si on ne peut pas y ajouter un nœud car si on l’ajoute l’ensemble n’est plus indépendant

Question 14

Ensemble indépendant maximum

Answer 14

Ensemble indépendant de plus grande cardinalité

Question 15

Ensemble indépendant maximal : Algorithme simple mais lent - Type d’algo

Answer 15

Algorithme faiblement synchronisé et très lent

Question 16

Ensemble indépendant maximal : Algorithme simple mais lent - Hypothèse

Answer 16

Chaque nœud a un identifiant unique

Question 17

Ensemble indépendant maximal Utilisation du coloriage - Type d’algo

Answer 17

Algorithme faiblement synchronisé
on a k rondes ( k = nombre de couleurs)

Question 18

Ensemble indépendant maximal Algorithme rapide- Type d’algo

Answer 18

*Algorithme faiblement synchrone et probabiliste
*Algo ne termine pas de façon déterministe

Question 19

Ensemble indépendant maximal Algorithme rapide- Nombre de rondes à la terminaison

Answer 19

*L’algorithme se termine en moyenne avec O(log n) rondes (n nombre de nœuds)

Question 20

Ensemble indépendant maximal :Autre algorithme rapide- Type d’algo

Answer 20

Algorithme faiblement synchrone et probabiliste

Question 21

Ensemble indépendant maximal :Autre algorithme rapide- Terminaison

Answer 21

Terminaison de l’algo non garanti
car en cas d’égalité des valeurs on n’avance pas

Question 22

Ensemble indépendant maximal :Autre algorithme rapide- Avantage

Answer 22

Meilleure proba d’avancer à chaque ronde

Question 23

Ensemble indépendant maximal :Autre algorithme rapide- Inconvénient

Answer 23

Rapide en moyenne