CM2 Partie1

Question 1

Graphe représentant le système distribué

Answer 1

• Graphe connexe
• Liens de communication bidirectionnels

Question 2

Comment est le canal?

Answer 2

le canal est FIFO

Question 3

Algorithme synchrone

Answer 3

• gouverné par une horloge globale externe
• Chaque noeud exécute une suite de rondes

Question 4

Que se passe-t-il dans une ronde dans une algorithme synchrone?

Answer 4

• chaque noeud envoie un message à chacun de ses voisins
• Tous les message envoyés dans une ronde sont reçus et traités dans la même ronde

Question 5

Algorithme partiellement synchrone

Answer 5

• Pas d’horloge globale extrene
• Un noeud peut passer à la ronde r+1 s’il a reçu un message de chacun de ses voisins r

Question 6

Algorithme asynchrone

Answer 6

• pas d’horloge globale externe
• L’avancement d’un nœud est lié à ses propres calculs et aux messages qu’il reçoit

Question 7

Principe de retransmission/abandon de messages

Answer 7

• La 1er fois que je reçois un message je retransmets
• Si je reçois encore le même message, je l’abandonne

Question 8

Apprendre le graphe sous-jacent au système distribué Complexité

Answer 8

• Nombre de messages transmis ≤ 2nm
  n->nbre de noeuds
  m->nbre de liens

Question 9

Une fois le graphe connu par tous les nœuds du système quelle est la 1ère approche que l’on peut imaginer?

Answer 9

• Choisir un nœud particulier (leader) dans le système
• Résoudre les problèmes avec des algorithmes séquentiels sur ce leader
• Le leader envoie les résultats aux nœuds du réseau
  *Faiblesse : peu robuste, peut-être coûteux en temps, peu tolérant aux pannes

Question 10

Une fois le graphe connu par tous les nœuds du système quelle est la 2ème approche que l’on peut imaginer?

Answer 10

• chaque nœud exécute l’algorithme séquentiel sur le graphe appris
• Il faut s’assurer que les exécutions séquentielles sur les différents nœuds vont donner un résultat cohérent
  *Faiblesse : peut-être coûteux en temps, peu robuste envers la dynamique

Question 11

Diffusion / Broadcast

Answer 11

• Un nœud (source) veut envoyer un message à tous les autres nœuds du système

Question 12

Hypothèses de la diffusion/broadcast

Answer 12

• Chaque nœud connaît son ID
• Le nombre de nœuds dans le système n’est pas connu
• Le graphe sous-jacent au système n’est pas connu

Question 13

Algorithme d’inondation

Answer 13

• ou flooding
• Utilisation du principe de retransmission / abandon des messages
• avec une seule source
• la source ne sait pas que et quand l’algorithme a terminé

Question 14

Comment réduire ce nombre d’envois du message dans l’algo d’inondation ?

Answer 14

Pour avoir une meilleure efficacité de l’algo de diffusion , nécessité de construire une topologie logique : arbre (couvrant)

Question 15

quand se termine l’algorithme d’inondation sur un arbre enraciné?

Answer 15

• quand les feuilles reçoivent le message
  *Mais la racine ne sait pas que l’algorithme est terminé

Question 16

complexité de l’algorithme d’inondation sur un arbre enraciné?

Answer 16

(n-1) envois de messages

Question 17

Si de nombreux messages à envoyer dans le fonctionnement du système distribué

Answer 17

• Rentable de construire un arbre couvrant
• Et de diffuser les messages sur cet arbre

Question 18

Convergecast

Answer 18

• Inverse de la diffusion
• Chaque nœud veut envoyer un message à un nœud spécifique ( par ex la racine de l’arbre)

Question 19

Algorithme Echo

Answer 19

• Initié par les feuilles de l’arbre
• Feuilles envoient leur message à leur parent
• Une fois les messages reçus de tous leurs fils, chaque nœud transmet un message à son parent ;
• message = données du nœud + données des fils

Question 20

quand se termine l’algorithme echo ?

Answer 20

• Une fois que la racine a reçu un message de chacun de ses fils, l’algorithme Echo est terminé
• la racine sait que l’algo est terminé, mais les autres nœuds de l’arbre ne le savent pas

Question 21

complexité de l’algorithme echo ?

Answer 21

n-1 messages

Question 22

L’algorithme echo est utilisé pour :

Answer 22

• La détection de terminaison, par la racine, d’algorithmes distribués
• Calculer le nombre de nœuds dans le système
• Calculer la valeur maximale/minimale d’un paramètre dans le système
• Calculer la somme des valeurs d’un paramètre

Question 23

Utilisation des arbres permet

Answer 23

• De communiquer (efficacement) de un vers tous
• De communiquer (efficacement) de tous vers un
• De récupérer des valeurs/paramètres de tous les nœuds
• De savoir si tous les nœuds ont terminé

Question 24

Construction d’un arbre couvrant Algorithme basé sur la diffusion et le convergecast : * Terminaison

Answer 24

Quand la racine reçoit un message Back de chacun de ses voisins
* Plusieurs arbres peuvent être construits
* Dépend de la vitesse des messages

Question 25

Arbre en largeur

Answer 25

• la source fait tout le travail
• on a une congestion réseau

Question 26

Arbre en profondeur

Answer 26

• arbre dans lequel on maximise la profondeur de l’arbre
• travail réparti
• pas de congestion réseau
• prend du temps

Question 27

Arbre couvrant en largeur : Algorithme sans contrôle centralisé

Answer 27

Algorithme «à la Bellman-Ford»
Complexité en temps : O(D)
Nombre de messages: O(nm)

Question 28

Arbre couvrant en largeur :
Algorithme avec contrôle centralisé

Answer 28

Algorithme «à la Dijkstra»
Exécution par vagues
Présence de l’algo Echo dans l’arbre p-1
Complexité temps : O(D*D)
nombre de messages: O(m+nD) avac m : join et nD : vague

Question 29

Une vague est différente de quoi?

Answer 29

d’une ronde

Question 30

Comparaison des complexités des deux algos

Answer 30

Bellman-Ford est plus bien en temps que le Djikstra
Bellman-Ford est moins bien en nombre de messages que le Djikstra

Question 31

Apprendre Le graphe sous jacent au système distribué Objectif

Answer 31

Découvrir le graphe et savoir qui sont les membres du système