CM2 Partie1 Flashcards
Graphe représentant le système distribué
- Graphe connexe
- Liens de communication bidirectionnels
Comment est le canal?
le canal est FIFO
Algorithme synchrone
- gouverné par une horloge globale externe
- Chaque noeud exécute une suite de rondes
Que se passe-t-il dans une ronde dans une algorithme synchrone?
- 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
Algorithme partiellement synchrone
- 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
Algorithme asynchrone
- pas d’horloge globale externe
- L’avancement d’un nœud est lié à ses propres calculs et aux messages qu’il reçoit
Principe de retransmission/abandon de messages
- La 1er fois que je reçois un message je retransmets
- Si je reçois encore le même message, je l’abandonne
Apprendre le graphe sous-jacent au système distribué Complexité
- Nombre de messages transmis ≤ 2nm
n->nbre de noeuds
m->nbre de liens
Une fois le graphe connu par tous les nœuds du système quelle est la 1ère approche que l’on peut imaginer?
- 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
Une fois le graphe connu par tous les nœuds du système quelle est la 2ème approche que l’on peut imaginer?
- 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
Diffusion / Broadcast
- Un nœud (source) veut envoyer un message à tous les autres nœuds du système
Hypothèses de la diffusion/broadcast
- 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
Algorithme d’inondation
- 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é
Comment réduire ce nombre d’envois du message dans l’algo d’inondation ?
Pour avoir une meilleure efficacité de l’algo de diffusion , nécessité de construire une topologie logique : arbre (couvrant)
quand se termine l’algorithme d’inondation sur un arbre enraciné?
- quand les feuilles reçoivent le message
*Mais la racine ne sait pas que l’algorithme est terminé
complexité de l’algorithme d’inondation sur un arbre enraciné?
(n-1) envois de messages
Si de nombreux messages à envoyer dans le fonctionnement du système distribué
- Rentable de construire un arbre couvrant
- Et de diffuser les messages sur cet arbre
Convergecast
- Inverse de la diffusion
- Chaque nœud veut envoyer un message à un nœud spécifique ( par ex la racine de l’arbre)
Algorithme Echo
- 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
quand se termine l’algorithme echo ?
- 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
complexité de l’algorithme echo ?
n-1 messages
L’algorithme echo est utilisé pour :
- 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
Utilisation des arbres permet
- 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é
Construction d’un arbre couvrant Algorithme basé sur la diffusion et le convergecast : * Terminaison
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
Arbre en largeur
- la source fait tout le travail
- on a une congestion réseau
Arbre en profondeur
- arbre dans lequel on maximise la profondeur de l’arbre
- travail réparti
- pas de congestion réseau
- prend du temps
Arbre couvrant en largeur : Algorithme sans contrôle centralisé
Algorithme «à la Bellman-Ford»
Complexité en temps : O(D)
Nombre de messages: O(nm)
Arbre couvrant en largeur :
Algorithme avec contrôle centralisé
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
Une vague est différente de quoi?
d’une ronde
Comparaison des complexités des deux algos
Bellman-Ford est plus bien en temps que le Djikstra
Bellman-Ford est moins bien en nombre de messages que le Djikstra
Apprendre Le graphe sous jacent au système distribué Objectif
Découvrir le graphe et savoir qui sont les membres du système
