Systèmes Répartis - PDF

# Systèmes Répartis ## H. Mansouri ## Laboratoire des Réseaux et des Systèmes Distribués ## LRSD ## Chapitre 1 ## Introduction aux Systèmes Répartis ### Plan 1. Système distribué: Définitions 2. Système distribué vs Système centralisé 3. Système distribué vs Système parallèle 4. Système distr...

# Systèmes Répartis ## H. Mansouri ## Laboratoire des Réseaux et des Systèmes Distribués ## LRSD ## Chapitre 1 ## Introduction aux Systèmes Répartis ### Plan 1. Système distribué: Définitions 2. Système distribué vs Système centralisé 3. Système distribué vs Système parallèle 4. Système distribué: Architecture 5. Système distribué: Caractéristiques 6. Système distribué synchrone vs asynchrone 7. Système distribué client serveur vs pair-à-pair 8. Système distribué : Distribution des données 9. Système distribué: Domaines d'applications 10. Système distribué: Avantages 11. Système distribué: Défis ## Système distribué : Définitions ### Définition de Tanenbaum Un système distribué est une collection d'ordinateurs indépendants qui apparaissent à l'utilisateur comme un seul système cohérent. ### Définition de Coulourise Un système distribué ou réparti est un système dont les composants sont répartis sur différents nœuds d'un réseau d'ordinateurs. Ces composants communiquent et coordonnent leurs actions uniquement par l'échange de messages. ## Système distribué vs Système centralisé ### Système centralisé: * Système logiciel s'exécutant sur une seule machine. * Les applications accèdent localement aux ressources nécessaires (données, code, périphériques, mémoire...) ### Système distribué: * Ensemble d'ordinateurs indépendants connectés en réseau et communiquent via ce réseau par envoi de messages. * Cet ensemble apparaît du point de vue de l'utilisateur comme une seule entité. ## Système distribué vs Système centralisé | Système Centralisé | Système Distribué | |---|---| | Les utilisateurs travaillent sur une seul machine | Les utilisateurs ont l'impression de travailler sur une seul machine | | Un seul OS | Différents OS | | Mémoire partagée | Mémoires individuelles | | Service Local | Retrouver le service! Qui le propose? | ## Système distribué vs Système parallèle ### Système parallèle : * Un système parallèle se compose de plusieurs processus s'exécutent par rapport à la même horloge et communiquent entre eux à l'aide d'une mémoire partagée. ### Système distribué : * Un système distribué se compose de plusieurs processus s'exécutent chacun par rapport à une horloge locale et communiquent entre eux par transmission de messages. ## Système distribué vs Système Parallèle | Système Parallèle | Système Distribué | |---|---| | Les processus ont accès à une mémoire commune | Pas de mémoire partagée, Chaque processus dispose d'une mémoire locale | | Les processus s'exécutent par rapport à la même horloge | Pas d'horloge globale | | L'état global est facilement observable | Le temps de propagation de message entre processus est non nul | ## Système distribué : Architecture **Application** **Middleware** **Système de communication** **Site A** **Site B** ### Middleware : * Masquer l'hétérogénéité des machines et des systèmes. * Masquer la répartition des données et des traitements. ## Système distribué : Caractéristiques ### Absence de base de temps commune (horloge commune) Chaque processus a une horloge locale, au fil du temps, la synchronisation des horloges locales se dégrade ⇒ Absence d'ordre d'exécution global. ### Absence de mémoire commune Chaque processus a une mémoire locale, pas de variables partagées, pas d'informations sur les autres processus ⇒ Absence d'état global. ## Système distribué synchrone vs asynchrone ### Système synchrone : * Le temps pour exécuter une étape du processus est compris entre une borne min et une borne max connues. * Un message émis est reçu dans un délai max connu. * L'horloge locale d'un processus dérive au plus d'une certaine durée connue et bornée du temps réel. ### Système asynchrone: il n'y aucune borne * Sur la durée d'exécution d'une étape du processus. * Sur le délai de réception d'un message. * Sur la dérive de l'horloge locale d'un processus par rapport au temps réel. ## Système distribué client serveur vs paire à paire ### Système client serveur : Le serveur gère toutes les exigences de traitement, de gestion des données et de calcul, qui sont disponibles à la demande pour les clients. ### Système paire à paire : Tous les nœuds peuvent jouer le rôle de client et de serveur simultanément ou à des moments différents. ## Système distribué : Distribution des données ### Duplication des données : * La donnée x est recopiée en n exemplaires x1,..., xn sur n sites * Assurer cohérence mutuelle des copies : x1 = x2 = ... = xn = x ### Partitionnement des données : * La donnée x est devisée en n portion x1,..., xn sur n sites * Assurer la cohérence de donnée: x1 + x2 + ... + xn = x ## Système distribué : Domaines d'applications * Calcul scientifique * Simulation distribuée * Multimédia * Téléconférence * Travail coopératif * Installations industrielles * Robotique * Télécommunications * Bourse, finance * Réalité virtuelle * Intelligence artificielle, Multi-agents * Jeux en réseaux * Guichet de banque. * Agence de voyage. * Serveur de fichiers. * WWW, FTP, Mail, DNS.. ## Système distribué : Avantages ### Economique: Excellent rapport performance/prix des microprocesseurs. ### Puissance de calcul: Un système multiprocesseur offre une puissance de calcul supérieure à celle d'un seul processeur. ### Distribution naturelle de certaines applications: Distribution géographique d'agences bancaires. ### Haute disponibilité: La défaillance d'une machine n'affecte pas les autres. ## Système distribué : Avantages * Partage de données entre les utilisateurs: Exemple: système de réservation aérienne. * Partage de périphériques coûteux: Exemple: imprimante, périphériques d'archivage. * Facilitation des communications entre personnes: Exemple: Courrier électronique. * Flexibilité (distribution de la charge): Permet d'exécuter un travail sur la machine la plus disponible. ## Système distribué : Défis * L'interopérabilité: La capacité à rendre compatibles des systèmes différents a fin de réduire le problème de l'hétérogénéité: réseaux, matériels (ordinateurs), systèmes d'exploitation, langages de programmation, implémentations faites par différents développeurs,... * L'ouverture: La possibilité d'ajout, de suppression ou de modification des ressources et services dans un système distribué. * Haute disponibilité: La défaillance d'un nœud n'entraîne pas l'indisponibilité du système sur les autres nœuds, seules les applications. ## Système distribué : Défis * L'invariance à l'échelle: Le système reste performant et d'un coût raisonnable lors d'une augmentation importante du nombre des utilisateurs et de ressources gérées.. * La gestion de la sécurité: Revient à assurer: La confidentialité, L'intégrité et la Disponibilité, * Le maintien de la consistance des ressources: La gestion des demandes concurrents d'accès à une ressources critique par plusieurs processus physiquement répartis. ## Système distribué : Défis * La transparence (flexibilité): La répartition des composants reste cachée pour l'utilisateur: Transparence d'accès, Transparence à la localisation. Transparence à la concurrence. Transparence à la duplication. Transparence aux pannes. Transparence à la mobilité. Transparence à la reconfiguration. Transparence à la modification de l'échelle. * La tolérance aux fautes et la gestion: Le système doit pouvoir fonctionner même en cas de défaillance de certains de ses éléments, # Systèmes Répartis ## H. Mansouri ## Laboratoire des Réseaux et des Systèmes Distribués ## LRSD ## Chapitre 2 ## Gestion du Temps dans les Systèmes Répartis ### Plan 1. Système distribué: Architecture 2. Système distribué: Processus 3. Système distribué: Canal de communication 4. Système Synchrone / Asynchrone 5. Etat global d'un système distribué 6. Temps physique 7. Temps physique: Algorithme de Cristian 8. Temps physique: Algorithme de Berkeley 9. Temps physique: Solution distribuée 10. Temps logique 11. Temps logique: chronogramme 12. Temps logique: dépendance causale 13. Graphe de dépendance causale 14. Délivrance FIFO vs Délivrance causale ## Système distribué: Architecture ## Système distribué: Processus Élément logiciel effectuant une tâche, un calcul par exemple, en exécutant un ensemble d'instructions, une instruction correspond à un événement local : * Événements interne, * Événements d'émission de message, * Événements de réception de message. ## Chaque processus : * Possède un identifiant unique, * Possède une mémoire et horloge locales, * Pas de connaissance de l'état des autres processus, * Les processus du système s'exécutent en parallèle. ## Système distribué: Canal de communication ### Caractéristiques : * Uni/Bidirectionnel: sens unique ou dans les deux sens. * Fiable/Non : perd/modifie ou pas des messages. * FIFO/Non: Ordre de réception par rapport à l'émission. * Synchrone/Asynchrone : l'émetteur et le récepteur se synchronisent pour réaliser l'émission et/ou la réception, ### Modèle de communication dans les systèmes distribués : * Bidirectionnel, non Fiable, non FIFO, asynchrone * Bidirectionnel, Fiable, FIFO, synchrone ## Etat global d'un système distribué Un état est la situation dans laquelle se trouve un processus à un instant donné (valeurs des variables, ensembles de données de la mémoire, ensemble de données circulant sur un canal de communication). * État local: propre à un processus * État global: propre au système, ## Problématique: Un état global est lié aux valeurs des variables à un temps (instant t), or chaque processus possède une mémoire et horloge physique locales et pas de mémoire et d'horloge globales dans un système distribué. ## Etat global d'un système distribué ### Solutions: * Synchronisation des horloges : * Synchronisation interne * Synchronisation externe * Utilisation de temps logique : * Horloge de Lamport * Horloge Vectorielle de Mattern * Horloge Matricielle ## Temps physique Une convention internationale définit le temps physique ou réel : * UTC: temps universel coordonné * Utilise une horloge atomique (dérive d'une microseconde tous les 3 ans environ) * L'heure universelle est diffusée par radio et satellites, * Un ordinateur muni d'un récepteur peut donc synchroniser périodiquement son horloge interne, et fonctionner comme serveur de temps sur un réseau local. ## Temps physique ### Le temps et l'état global sont difficiles à réaliser dans les SDs : * Les processus sont distribués géographiquement, * Le taux d'occurrence des événements est élevé, * Les durées d'exécution des événements est très courtes, * Le délai de transfère des messages n'est pas négligeable, ### On ne peut qu'approximer la vision globale en : * Simulant un temps global via des horloges logiques, * Simulant un état global via des Snapshots. ## Temps physique * Les horloges physiques des sites dérivent constamment. ## Temps physique: Algorithme de Cristian ### Utiliser le temps d'un serveur comme référentiel de temps: * Un client demande, via un message, le temps à un serveur, * Le serveur répond en envoyant un message contenant le temps courant T, * Le client utilise la valeur T reçue pour mettre à jour son horloge. ## Temps physique: Algorithme de Cristian * (T1-T0)/2 est l'estimation du coût dans chaque direction, * Le client doit donc ajuster son horloge à: Tclient = Tserveur + (T1-to)/2 * La précision du résultat est donc: ± (T1-to)/2 - Tmin ## Temps physique: Algorithme de Cristian * Un client envoie sa requête à 10:10:15.100 (to) * Il reçoit la réponse du serveur à 10:10:15.900 (T1) * La réponse contient: 10:11:25.300 (Tserveur) * Temps écoulé est: 10:10:15.900 - 10:10:15.100 = 800 ms * Meilleure estimation: Le temps à été généré il y a 400 ms * Ajuster le temps client à: 10:11:25.300 + 400 = 10:11:25.700 * Si le temps min de transit d'un message est 200 ms alors la précision est : (T1-to)/2-Tmin = 400-200 = ± 200 ms ## Temps physique: Algorithme de Berkeley * Un processus Pi est élu comme un serveur reference de temps, * Pi demande périodiquement le temps des autres processus, * Une fois Pi reçus tous les temps, il élimine les temps des horloges trop déviantes, et calcule la moyenne, * Pi diffuse le temps moyen aux autres processus pour ajuster leurs horloges. ## Temps physique: Solution distribué * Christian et Berkeley sont des algorithmes centralisés, * Chaque processus diffuse son heure au début d'une période de temps, * Chaque processus collecte tous les messages arrivés durant un intervalle, * Chaque processus exécute un même algorithme à partir des n données reçues pour l'obtention d'une heure moyenne. ## Temps logique * Créer un temps qui n'est pas lié au temps physique * Créer un ordonnancement logique en fonction des événements locaux des processus et des messages envoyés et reçus. ## Trois approches principales : * Horloge scalaire (Lamport) * Horloge vectorielle (Mattern) * Horloge matricielle ## Temps logique: chronogramme * Décrit l'ordonnancement temporel des événements des processus et des échanges de messages. * Chaque processus est représenté par une ligne. ## Trois types d'événements signalés sur une ligne : * Émission d'un message à destination d'un autre processus. * Réception d'un message venant d'un autre processus. * Événement interne dans l'évolution du processus ## Temps logique: chronogramme * exy avec x le numéro du processus et y le numéro de l'événement pour le processus, dans l'ordre croissant. ## Temps logique: dépendance causale * Il y a une dépendance causale entre 2 événements si un événement doit avoir lieu avant l'autre. ## Temps logique: dépendance causale * e11 → e12 * e12 → e34 * e11 → e35 * e12 || e32 ## Graphe de dépendance causale ## Délivrance FIFO vs Délivrance causale ### Délivrance FIFO: si 2 messages sont envoyés successivement de Pi vers Pj alors le premier sera délivré avant le deuxième, ### Délivrance causale: si l'envoi d'un message m1 par Pi à destination Pn précède (causalement) l'envoi de m2 par Pj à destination Pn alors le m1 sera délivré avant m2 à Pn, # Systèmes Répartis ## H. Mansouri ## Laboratoire des Réseaux et des Systèmes Distribués ## LRSD ## Chapitre 3 ## Horloges Logiques dans les Systèmes Répartis ### Plan 1. Système distribué, Processus, Canal de communication 2. Système synchrone / Asynchrone 3. État et horloge globales 4. Temps logique et horloge logique 5. Délivrance FIFO vs Délivrance causale 6. Horloge scalaire (Lamport) 7. Horloge vectorielle (Mattern) 8. Horloge matricielle ## Horloge scalaire (Horloge de Lamport) ### Horloge logique respectant les dépendances causales: * Une date (estampille) est associée à chaque événement : couple (Np, Nv) * Np: numéro du processus * Nv: numéro d'événement * Les dates des événements d'un même processus sont différentes. * Les dates des événements d'envoi et de réception d'un même message sont différentes. ## Horloge de Lamport * Un compteur entier Hi est conservé sur chaque processus Pi * Un événement e sur le processus Pi est daté par H(e) = Hi * Initialisation * Hi = 0, pour tout i * A chaque événement local e sur Pi * Hi(e) := Hi(e) + 1; //e est daté par Hi * Chaque message est estampillé par la date de son émission sur le processus Pi : Hi(émission) * A la réception de e sur un processus Pj: Hj(réception) := max (Hj, Hi(émission))+ 1 ## Horloge de Lamport * Ordonnancement partiel: * e → K⇒ Hi(e) < Hj(k) * Ordonnancement total: * e → k⇔ (Hi(e) < Hj(k)) ou (Hi(e) = Hj(k) et i < j) ## Horloge de Lamport * Limite: * e → k⇒ H(e) < H(k) * H(e) < H(k) ⇒ e → k ???!!! * Ordonnancement artificielle des événements concurrents. * ek (Hi(e) < Hj(k)) ou (Hi(e) = Hj(k) et i < j) * Ne permet pas d'assurer l'ordre FIFO ni la délivrance causale. ## Horloge de Mattern * Horloge qui assure la réciproque de la dépendance causale: * Hi(e) < Hj(k) ⇔ e → K * Permet également de savoir si 2 événements sont concurrents. * Localement, chaque processus Pi a un vecteur Vi de taille égale au nombre de processus. * Vi[j] contient la valeur de l'horloge du processus Pj. ## Horloge de Mattern * Initialement: * Vi = 0 * A chaque événement local à Pi : * Vi[i] := Vi[i] + 1 * Chaque message m porte une estampille de l'émetteur Pi : Vm = Vi * A la réception de Vm par un site Pj : * Vj[j] := Vj[j] + 1; * Vj[K] := max (Vj[K], Vm[K]) pour k∈[1,n] k ≠ j ## Horloge de Mattern * Ordonnancement partiel: * Vk: Vi[k] ≤ Vj[k] = Vi ≤ Vj * Vi ≤ Vj∧∃r/Vi[r] <Vj [r] ⇒ Vi < Vj * ¬(Vi < Vj) et (Vj < Vi) ⇒ Vi || Vj ## Horloge de Mattern * Limite * Ne permet pas de définir un ordre global total * Ne permettent pas de garantir une délivrance causale des messages ## Horloge Matricielle * n processus dans le système * Mi[n,n] pour chaque processus Pi : * Ligne i: informations sur les événements de Pi * Mi[i,i]: nombre d'événements sur Pi * Mi[i,j]: nombre de message envoyer par Pi à Pj * Ligne j: informations que l'on sait sur les événements de Pj : * Mi[j,j]: nombre d'événements que l'on sait sur Pj * Mi[j,k]: nombre de message que l'on sait que Pj a envoyé à Pk ## Horloge Matricielle * Exemple avec 3 processus: ## Horloge Matricielle Sur le processus Pi, la matrice Mi va : * mémoriser le nombre de messages que le processus Pi a envoyé aux différents autres processus, * l'élément diagonal représente la connaissance qu'a Pi du nombre d'événements locaux qui se sont déjà produits sur les différents processus Pj, * mémoriser, pour chacun des autres processus Pj, le nombre de messages émis par ce site dont le processus Pi a connaissance, * Ainsi, la valeur Mi[j,k] donne le nombre de messages en provenance du processus Pj délivrables sur le processus Pk dont le processus Pi a connaissance. ## Horloge Matricielle * Initialement : * Mi = 0 * A chaque événement local à Pi : * Mi[i,i] := Mi[i,i] + 1 * A Chaque envoi de message de Pi vers Pj : * Mi[i,i] := Mi[i,i] + 1 * Mi[i,j] := Mi[i,j] + 1 * Chaque message m porte l'estampille de l'émetteur Pi: Mm= Mi * A la réception de Mm par un site Pj : * if ((Mm[i,j] = Mj[i,j] + 1) et (∀k ≠ i/j, Mm[k,j] ≤ Mj[k,j])) { * Mj[j,j] := Mj[j,j] + 1 * Mj[k,r] := max (Mj[k,r], Mm [k,r]) pour k/r ∈ [1,n] k/r≠j } ## Horloge Matricielle Le récepteur du message m, soit Pj retarde la délivrance de m jusqu'à ce que les deux conditions suivantes soient satisfaites : * La condition 1: Mm[i,j] = Mj[i,j] + 1 * Assure que Pj a reçu tous les messages émanant de Pi et précédant m. * La condition 2: ∀ k≠ i/j, Mm[k,j] ≤ Mj[k,j] * Assure que Pj a reçu tous les messages envoyons avant l'envoi de m. ## Horloge Matricielle * Les messages retardés sont mis en attente au niveau du processus dans une file d'attente triée selon leurs estampilles matricielle. ## Protocole Birman-Schiper-Stephenson * Les processus se transmettent les messages par diffusion. * L'implémentation du protocole est fondé sur les règles suivantes: ### Règle1: Avant la diffusion d'un message m, le processus émetteur Pi incrémente sont horloge vectorielle Vi tel que: Vi[i] := Vi[i] + 1, L'estampille est intégrée dans m: Vm = Vi[i] ### Règle 2: Le récepteur du message m, soit Pj retarde la délivrance de m jusqu'à ce que les conditions suivantes soient satisfaites: * Vj[i] = Vm[i]-1 * ∀ke [1,2,...n]-{i}, Vj[k] ≥ Mm[k] ## Protocole Birman-Schiper-Stephenson * La condition 1 de la règle 2 assure que Pj a reçu tous les messages émanant de Pi et précédant m, et la condition 2 assure que Pj a reçu tous les messages qui sont reçus par Pi avant d'avoir émis m. * Les messages retardés sont mis en attente au niveau du processus dans une file d'attente triée selon leurs estampilles vectorielles. ### Règle 3: Quand un message est délivré au niveau de Pj, son horloge vectorielle Vj est mise à jour selon la régle: Vj[k] := max(Vj[k], Vm[k]) ## Protocole Birman-Schiper-Stephenson # Systèmes Répartis ## H. Mansouri ## Laboratoire des Réseaux et des Systèmes Distribués ## LRSD ## Chapitre 4 ## État global dans les Systèmes Répartis ### Plan 1. État Global: Problématique 2. État Global: Applications 3. État Global: Coupure 4. État Global: Caractéristique 5. État Global: Cohérence 6. Sauvegarde non coordonnée 7. Sauvegarde coordonnée 8. Datation de Coupure 9. Algoritme de Chandy-Lamport 10. Algoritme de Chandy-Lamport: Exemple ## État Global: Problématique Dans un systèmes réparti, un processus a besoin de connaître les états de tous ces partenaires pour pouvoir prendre une décision locale impactant l'état global du système. ### Problème : * L'absence de mémoire partagé résulte une connaissance incorrecte ou approximative de la valeur des objets distribués. * L'absence d'horloge globale (commune) induit l'absence d'une notion de temps cohérent. * Temps de transfert des messages est non borné. ## Comment donc collecter un état global cohérent ? ## État Global: Problématique Soit un système bancaire distribué gérant deux comptes C1 et C2 reliés chacun par un canal d'entrée et un canal de sortie. Le transfert d'argent est représenté sur le schéma suivant: ## État Global: Applications * Détecter des propriétés caractérisant l'exécution (terminaison, inter-blocage, vérification d'assertions, etc.) ⇒ * Effectuer des mesures de performances * Trouver des états cohérents à partir desquels on peut reprendre un calcul distribué en cas de faute ou défaillance. ## État Global: Coupure * Calcul distribué = ensemble E d'événements * Coupure C est un sous-ensemble fini de E tel que: si a et b deux événements du même processus alors : * a ∈ Cet ba⇒bEC * Etat associé à une coupure: l'événement le plus récent pour chaque processus ## État Global: Coupure * État = { e11, e12, e13, e21, e22, e23, e31, e32, e33, e34 } * Coupure = (e13, e23, e34) ## État Global: Caractéristique Chaque processus et chaque canal possède à tout moment un état local : * L'état local d'un processus Pi résulte de son état initial et de la séquence d'événements sur ce processus : * Événement locale * Événement d'émission de message * Événement de réception de message * L'état d'un canal de communication entre deux processus Pi et Pj est l'ensemble des messages en transit sur ce canal, c'est à dire qui ont été émis par le processus Pi et n'ont pas encore été reçus par le processus Pj. ## État Global: Caractéristique * Un état global est l'ensemble des états locaux des processus plus les états des canaux de communication. ## État Global: Cohérence * ∀m: Send (m) ∈ GS ^ Receive (m) & GS * m: Receive (m) ∈ GS → Send (m) ∈ GS me GS ## État Global: Cohérence * Dans un état global incohérent, il existe au moins un message m dont l'évènement de réception est enregistré mais l'évènement d'émission associé ne l'est pas. Ce message est appelé message orphelin. * Un état global est cohérent si et seulement si pour tout message m, si l'événement de réception de mest enregistrer alors l'évènement d'émission correspondant est enregistré dans l'état global * Un état global est dit fortement cohérent si tout message émis est reçu. * Un état global est dit cohérent transitaire si au moins un message m dont l'évènement d'émission est enregistré mais l'évènement de réception associé ne l'est pas. ## État Global: Cohérence * GS1={C11, C21, C31} est fortement cohérent. * GS2={C11, C22, C32} est incohérent. * GS3={C12, C23, C33} est cohérent transitaire. ## Sauvegarde non coordonnée * Chaque processus sauvegarde son état local sans coordination : * Pas de messages de coordination supplémentaires. * Donner aux processus une autonomie maximale. * ✓ La sauvegarde d'un point de reprise au moment opportun. * X Produire des points de reprise inutiles. * X Possibilité de l'effet domino: ## Sauvegarde coordonnée * Les processus se coordonnent avant de sauvegarder leurs états. * Garantir la cohérence de l'état enregistré. * Recouvrement simple. * L'effet domino n'est pas possible. * ✔ Réduire le coûts de stockage. * X Échange de messages de coordination supplémentaires. ## Datation de Coupure * Horloge de Mattern: permet de dater une coupure * Soit un système réparti de N processus, * C = {e1,..., eN} une coupure, ei l'événement le plus récent pour le processus Pi, * V(ei) la datation de ei et V(C) la datation de la coupure : V(C) = (max V(e1), ..., max V(en)) * Cest cohérent si : V(C) = (V(e1)[1], ..., V(ei)[i], ..., V(en)[n]) ## Datation de Coupure * Coupure C1 = (e13, e22, e33) : * V(e13) = (3,0,0), V(e22) = (1,2,1), V(e33) = (0,0,3) * V(C) = (max(3,1,0), max(0,2,0), max(0,1,3)) = (3,2,3) * V(C)[1] = V(e13)[1], V(C)[2] = V(e22)[2], V(C)[3] = V(e33)[3] cohérent ## Datation de Coupure * Coupure C2 = (e13, e23, e34): * V(e13) = (3,0,0), V(e23) = (1,3,5), V(e34) = (2,0,4) * V(C) = (max(3,1,2), max(0,3,0), max(0,5,4)) = (3,3,5) * V(C)[1] = V(e13)[1], V(C)[2] = V(e23)[2], V(C)[3] ≠ V(e34)[3] incohérente ## Algoritme de Chandy-Lamport ### L'idée principale : * si nous savons que tous les messages qui ont été envoyés par chaque processus ont été reçus par un autre, nous pouvons alors enregistrer l'état global du système. ### Hypothèses de l'algorithme : * Sur un canal de communication entre chaque deux processus, les messages sont reçus dans le même ordre qu'ils sont envoyés (FIFO). ## Algoritme de Chandy-Lamport ### Fonctionnement : * Tout processus du système distribué peut initier cet algorithme d'enregistrement d'état global (Checkpointing) à l'aide d'un message spécial appelé MARKER. * Ce marqueur traverse le système distribué sur tous les canaux de communication et amène chaque processus à enregistrer son propre état. * À la fin, l'état de l'ensemble du système (état global) est enregistré. * L'algorithme n'interfère pas avec l'exécution normale des processus. ## Algoritme de Chandy-Lamport À l'initialisation de l'algorithme par un processus Pi : * Pi enregistre son propre état local. * Envoi un marqueur sur chaque canal sortant avant d'envoyer tout autre message. * Commencer l'enregistrement de l'état de chaque canal entrant À la réception d'un marqueur par un processus Pj provenant de Pi : * Si le processus Pj n'a pas encore enregistré son propre état local alors: * Exécuter les Règles d'envoi de marqueur par un processus Pj. * Si le processus Pj a déjà enregistré son état : * Arrêter l'enregistrement de l'état des canaux d'entrée du Pi. À la réception de tous les marqueurs parr un processus Pj : * Valider l'état local de Pj ## Algoritme de Chandy-Lamport ## Algoritme de Chandy-Lamport: Exemple ## Algoritme de Chandy-Lamport ### L'état global est l'ensemble des états locaux des processus plus les états des canaux de communication.