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
