Introduction aux Systèmes Distribués

Gestion du temps & état global dans

un système distribué

1
 Systèmes distribués
 Système distribué en opposition à système
centralisé
 Système centralisé : tout est localisé sur la même
machine et accessible par le programme
 Système logiciel s'exécutant sur une seule machine
 Accédant localement aux ressources nécessaires
(données, code, périphériques, mémoire ...)
 Système distribué : une définition parmi d'autres
 Ensemble d'ordinateurs indépendants connectés en
réseau et communiquant via ce réseau
 Cet ensemble apparaît du point de vue de l'utilisateur
comme une unique entité
2
 Systèmes distribués
 Vision matérielle d'un système distribué : architecture
matérielle
 Ordinateurs standards connectés en réseau
 Vision logicielle d'un système distribué
 Système logiciel composé de plusieurs entités s'exécutant
indépendamment et en parallèle sur un ensemble d'ordinateurs
connectés en réseau
 De par leur nature, les systèmes distribués sont dans un
cadre différent par rapport aux systèmes centralisés
 Concurrence
 Les éléments formant le système s'exécutent en parallèle et de
manière autonome
3
  Pas d'état ou d'horloge globale commune
 Points de problèmes de fiabilité en nombre accru
 Problème matériel d'une machine
 Problème de communication via le réseau

 Communication est un point crucial

 Potentiellement non fiable
 Temps de communication non négligeables

4
 Transparences(1)
 Transparence
 Fait pour une fonctionnalité, un élément d'être invisible
ou caché à l'utilisateur ou un autre élément formant le
système distribué
 But est de cacher l'architecture, le fonctionnement de
l'application ou du système distribué pour apparaître
à l'utilisateur comme une application unique
cohérente
 L'ISO définit plusieurs transparences
 Accès, localisation, concurrence, réplication,
mobilité, panne, performance, échelle

5
 Transparences (2)
 Transparence d'accès
 Accès à des ressources distantes aussi facilement que
localement
 Accès aux données indépendamment de leur
format de représentation
 Transparence de localisation
 Accès aux éléments/ressources indépendamment de
leur localisation
 Transparence de concurrence
 Exécution possible de plusieurs processus en parallèle
avec utilisation de ressources partagées
 Transparence de réplication
 Possibilité de dupliquer certains éléments/ressources
pour augmenter la fiabilité
6
 Transparences (3)
 Transparence de mobilité
 Possibilité de déplacer des éléments/ressources
 Transparence de panne
 Doit supporter qu'un ou plusieurs éléments tombent
en panne
 Transparence de performance
 Possibilité de reconfigurer le système pour en
augmenter les performances
 Transparence d'échelle
 Doit supporter l'augmentation de la taille du système
(nombre d'éléments, de ressources ...)
7
 Transparences (4)
 Un système donné va offrir un certain nombre
de transparences
 Souvent au minimum transparences de
localisation, d'accès et de concurrence
 Système distribué ouvert
 Peut être étendu en nombre d'éléments matériels
le constituant
 Possibilité d'ajouts de nouveaux services ou de ré-
implémentation de services existants au niveau
logiciel
 Fonctionnement se base sur des interfaces
d'interactions clairement définies
8
 Algorithmique distribuée (1)
 Développement d'algorithmes dans le contexte
particulier des systèmes distribués
 Contraintes à prendre en compte dans ce contexte
 Concurrence
 Les éléments formant le système s'exécutent en parallèle et de
manière autonome
 Pas d'état ou d'horloge globale commune
 Points de problèmes de fiabilité en nombre accru
 Problème matériel d'une machine
 Problème de communication via le réseau
 Problème logiciel sur un des éléments du système
 Communication est un point crucial
 Potentiellement non fiable
 Temps de communication non négligeables
9
 Algorithmique distribuée (2)
 Développement d'algorithmes dédiés aux systèmes distribués et
prenant en compte les spécificités de ces systèmes
 On y retrouve notamment des adaptations de problèmes
classiques en parallélisme
 Exclusion mutuelle, élection (d'un maître) ...
 Mais aussi des problèmes typiques des systèmes distribués
 Horloge globale, état global, diffusion causale, consensus ...
 S'intéresse principalement à deux grandes familles de problèmes
 Synchronisation et coordination entre processus distants
 Entente sur valeurs communes et cohérence globale dans un contexte
non fiable (crash de processus, perte de messages ...)
 Dans ce cours
 Introduction à l'algorithmique distribuée avec les problèmes
d'horloge et d'état globaux
10
 Processus
 Processus
 Élément logiciel effectuant une tâche, un calcul
 Exécution d'un ensemble d'instructions
 Une instruction correspond à un événement local au processus
 Dont les événements d'émission et de réception de messages
 Les instructions sont généralement considérées comme
atomiques
 Il possède une mémoire locale
 Il possède un état local
 Ensemble de ses données et des valeurs de ses variables locales
 Il possède un identifiant qu'il connaît
 Pas ou peu de connaissance des autres processus du
système et de leur état
 Les processus d'un système s'exécutent en parallèle
11
 Canaux (1)
 Canal de communication
 Canal logique de communication point à point
 Pour communication entre 2 processus
 Transit de messages sur un canal
 Caractéristiques d'un canal
 Uni ou bi-directionnel
 Fiable ou non : perd/modifie ou pas des messages
 Ordre de réception par rapport à l'émission
 Exemple : FIFO = les messages sont reçus dans l'ordre où ils sont émis
 Synchrone ou asynchrone
 Synchrone : l'émetteur et le récepteur se synchronisent pour réaliser
l'émission et/ou la réception
 Asynchrone : pas de synchronisation entre émetteur et récepteur
 Taille des tampons de message cotés émetteur et récepteur
 Limitée ou illimitée
12
 Canaux (2)
 Caractéristiques d'un canal
 Modèle généralement utilisé
 Fiable, FIFO, tampon de taille illimitée, asynchrone (en émission
et réception) et bidirectionnel
 Variante courante avec réception synchrone
 Exemple : modèle des sockets TCP
 Fiable
 FIFO
 Bidirectionnel
 Synchrone pour la réception
 On reçoit quand l'émetteur émet
 Sauf si données non lues dans le tampon coté récepteur
 Asynchrone en émission
 Emetteur n'est pas bloqué quand il émet quoique fasse le
récepteur
13
 Système synchrone / Asynchrone
 Un modèle synchrone est un modèle où les
contraintes temporelles sont bornées
 On sait qu'un processus évoluera dans un temps borné
 On sait qu'un message arrivera en un certain délai
 On connaît la limite de dérive des horloges locales
 Un modèle asynchrone n'offre aucune borne
temporelle
 Modèle bien plus contraignant et rendant impossible ou
difficile la réalisation de certains algorithmes distribués
 Exemple : ne sait pas différencier en asynchrone
 Le fait qu'un processus est lent ou est planté
 Le fait qu'un message est long à transiter ou est perdu
14
 État et horloge globales
 Pour chaque processus du système
 État local : valeur des variables du processus à un instant t
 État global du système
 Valeur de toutes les variables de tous les processus du
système à un instant t
 Problème
 Un état est lié à un instant t
 Mais
 Chaque processus à une horloge physique locale
 Pas d'horloge globale dans un système distribué
 La définition d'un état global est possible seulement si on
est capable de définir un temps global
15
 Temps
 Définir un temps global cohérent et « identique »
(ou presque) pour tous les processus
 Soit synchroniser au mieux les horloges physiques
locales avec une horloge de référence ou entre elles
 Soit créer un temps logique
 Synchronisation des horloges physiques locales
 But est d'éviter qu'une horloge locale dérive trop par
rapport à un référentiel de temps
 La dérive est bornée en augmentation et en diminution
 Deux modes
 Synchronisation interne
 Synchronisation externe
16
 Temps logique
 Temps logique
 Temps qui n'est pas lié à un temps physique
 But est de pouvoir préciser l'ordonnancement de
l'exécution des processus et de leur communication
 En fonction des événements locaux des processus, des
messages envoyés et reçus, on créé un
ordonnancement logique
 Création horloge logique
 Deux approches principales
 Horloge de Lamport : méthode par estampille
 Horloge de Mattern : horloge vectorielle
17
 Temps logique : chronogramme
 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
 Les messages échangés doivent respecter la topologie
de liaison des processus via les canaux

18
 Temps logique : chronogramme
 Trois processus tous reliés entre-eux par des canaux
 Temps de propagation des messages quelconques et
possibilité de perte de message

m6

19
 Temps logique : chronogramme
 Exemples d'événements
 Processus P1
 e11 : événement d'émission du message m1 à destination du
processus P2
 e13 : événement interne au processus
 e14 : réception du message m4 venant du processus P3
 Processus P2 : message m5 envoyé avant m6 mais m6
reçu avant m5
 Processus P3 : le message m7 est perdu par le canal de
communication
 Règle de numérotation d'un événement
 exy avec x le numéro du processus et y le numéro de
l'événement pour le processus, dans l'ordre croissant
20
 Temps logique : dépendance causale
 Relation de dépendance causale
 Il y a une dépendance causale entre 2 événements si
un événement doit avoir lieu avant l'autre
 Notation : e → e'
 e doit se dérouler avant e'
 Si e → e', alors une des trois conditions suivantes
doit être vérifiée pour e et e'
 Si e et e' sont des événements d'un même processus, e
précède localement e'
 Si e est l'émission d'un message, e' est la réception de
ce message
 Il existe un événement f tel que e → f et f → e'
21
 Temps logique : dépendance causale
 Sur exemple précédent
 Quelques dépendances causales autour de e12
 Localement : e11 → e12, e12 → e13
 Sur message : e12 → e34
 Par transitivité : e12 → e35 (car e34 → e35) et e11 → e13
 Dépendance causale entre e12 et e32 ?
 A priori non : absence de dépendance causale
 Des événements non liés causalement se déroulent en parallèle
 Relation de parallélisme : ||
 e || e' ⇔ ¬((e → e') v (e' → e))
 Parallélisme logique : ne signifie pas que les 2 événements
se déroulent simultanément mais qu'ils peuvent se dérouler
dans n'importe quel ordre.
22
 Temps logique : dépendance causale
 Ordonnancement des événements
 Les dépendances causales définissent des ordres
partiels pour des ensembles d'événements
 But d'une horloge logique
 Créer un ordre total global sur tous les événements de
tous les processus
 Horloge logique
 Fonction H(e) : associe une date à chaque événement
 Respect des dépendances causales
 e → e' ⇒ H(e) < H(e')
 H(e) < H(e') ⇒ ¬ (e' → e), C'est-à-dire : soit e → e', soit e || e'
23
 Horloge de Lamport
 Lamport, 1978
 Horloge de Lamport : horloge logique respectant les
dépendances causales
 Une date (estampille) est associée à chaque évenement :
couple (s, nb)
 s : numéro du processus
 nb : numéro d'événement

 Invariant sur les dates

 Pour deux dates d'un même processus, les numéros de
ces événements sont différentes
 Il n'y pas deux événements locaux ayant le même numéro.
24
 Horloge de Lamport
 Création du temps logique
 Localement, chaque processus Pi possède une horloge
locale logique Hi, initialisée à 0
 Sert à dater les événements
 Pour chaque événement local de Pi
 Hi = Hi + 1 : on incrémente l'horloge locale
 L'événement est daté localement par Hi
 Émission d'un message par Pi
 On incrémente Hi de 1 puis on envoie le message avec (i, Hi)
comme estampille
 Réception d'un message m avec estampille (s, nb)
 Hi = max(Hi, nb) +1 et marque l'événement de réception avec Hi
 Hi est éventuellement recalée sur l'horloge de l'autre processus
avant d'être incrémentée
25
 Horloge de Lamport
 Exemple : chronogramme avec ajouts des estampilles

 Date de e23 : 6 car le message m5 reçu avait une valeur de 5 et

l'horloge locale est seulement à 3
 Date de e34 : 4 car on incrémente l'horloge locale vu que sa valeur est
supérieure à celle du message m3
 Pour e11, e12, e13 ... : incrémentation de +1 de l'horloge locale
26
 Horloge de Lamport
 Ordonnancement global
 Valeur de Hi permet de savoir si un événement a lieu
avant un autre ou pas, qu'il s'agisse d'événements
 Du même processus
 De processus différents
 Ordre total, noté e << e' : e s'est déroulé avant e'
 Soit e événement de Pi et e' événement de Pj :
e << e' ⇔ (Hi(e) < Hj(e')) v (Hi(e) = Hj(e') avec i < j)
 Localement (si i = j), Hi donne l'ordre des événements du processus
 Les 2 horloges de 2 processus différents permettent de déterminer
l'ordonnancement des événements des 2 processus
 Si égalité de la valeur de l'horloge, le numéro du processus est utilisé
pour les ordonner
27
 Horloge de Lamport
 Limites de l'horloge de Lamport
 L'ordonnancement global obtenu est arbitraire et n'est
pas forcément celui obtenu en pratique
 H(e32) = 2 et H(e22) = 3 pourtant e22 est exécuté en pratique
avant e32
 Ordre total global obtenu pour l'exemple
 e11 << e31 << e12<< e21 << e32 << e13 << e22 << e33 << e14
<< e34 << e35 << e23 << e24 << e15
 D'autres sont valides ...
 Horloge de Lamport respecte les dépendances causales
mais avec e et e' tel que H(e) < H(e') on ne peut rien dire
sur la dépendance entre e et e'
 Dépendance causale directe ou transitive entre e et e' ?
 Exemple : H(e32) = 2 et H(e13) = 3 mais on a pas e32→ e13
28
 Horloge de Mattern
 Horloge de Mattern & Fidge, 1989-91
 Horloge qui assure la réciproque de la dépendance causale
 H(e) < H(e') ⇒ e → e'
 Permet également de savoir si 2 événements sont
parallèles (non dépendants causalement)
 Ne définit par contre pas un ordre total global

 Principe
 Utilisation d'estampilles sur les messages
 Vecteur V de taille égale au nombre de processus
 Localement, chaque processus Pi a un vecteur Vi
 Pour chaque processus Pi, chaque case Vi[ j ] du vecteur
contiendra des valeurs de l'horloge du processus Pj
29
 Horloge de Mattern
 Fonctionnement de l'horloge
 Initialisation : pour chaque processus Pi, Vi =(0, ... , 0)
 Pour un processus Pi, à chacun de ses événements
(local, émission, réception) :

Vi [ i ] = Vi [ i ] + 1

Incrémentation du compteur local d'événement

Si émission d'un message, alors Vi est envoyé avec le message
 Pour un processus Pi, à la réception d'un message m contenant un
vecteur Vm, on met à jour les cases j ≠ i de son vecteur local Vi
 ∀j : Vi [ j ] = max ( Vm [ j ], Vi [ j ])
 Mémorise le nombre d'événements sur Pj qui sont sur Pj dépendants
causalement par rapport à l'émission du message
 La réception du message est donc aussi dépendante causalement
de ces événements sur Pj
30
 Horloge de Mattern
 Exemple : chronogramme d'application horloge de mattern
 Même exemple que pour horloge de Lamport

31
 Horloge de Mattern
 Relation d'ordre partiel sur les dates
 V ≤ V' défini par ∀i : V[ i ] ≤ V'[ i ]
 V < V' défini par V ≤ V' et ∃j tel que V [ j ] < V' [ j ]
 V || V' défini par ¬( V < V' ) ∧ ¬( V' < V )

 Dépendance et indépendance causales

 Horloge de Mattern assure les propriétés suivantes, avec e
et e' deux événements et V(e) et V(e') leurs datations
 V(e) < V(e') ⇒ e → e'
 Si deux dates sont ordonnées, on a forcément dépendance causale
entre les événements datés
 V(e) || V(e') ⇒ e || e'
 Si il n'y a aucun ordre entre les 2 dates, les 2 événements sont
indépendants causalement
32
 Horloge de Mattern
 Retour sur l'exemple
 V(e13) = (3,0,0), V(e14) = (4,0,3), V(e15) = (5,4,5)
 V(e13) < V(e14) donc e13 → e14
 V(e14) < V(e15) donc e13 → e15
 V(e35) = (2,0,5) et V(e23) = (2,3,5)
 V(e35) < v(e23) donc e35 → e23
 L'horloge de Mattern respecte les dépendances causales
des événements
 Horloge de Lamport respecte cela également
 V(e32) = (0,0,2) et V(e13) = (3, 0, 0)
 On a ni V(e32) < V(e13) ni V(e13) < V(e32) donc e32 || e13
 L'horloge de Mattern respecte les indépendances causales
 L'horloge de Lamport impose un ordre arbitraire entre les événements
indépendants causalement
33
 Horloge de Mattern
 Limite de l'horloge de Mattern
 Ne permet pas de définir un ordre global total
 En cas de nombreux processus, la taille du vecteur
peut-être importante et donc des données à
transmettre relativement importante

34
 État Global
 État global
 État du système à un instant donné
 Buts de la recherche d'états globaux
 Trouver des états cohérents à partir desquels on peut reprendre
un calcul distribué en cas de plantage du système
 Détection de propriétés stables, du respect d'invariants
 Faciliter le debugging et la mise au point d'applications
distribuées
 Défini à partir de coupures
 Coupure
 Photographie à un instant donné de l'état du système
 Définit les événements appartenant au passé et au futur
par rapport à l'instant de la coupure.
35
 Coupure
 Définition coupure
 Calcul distribué = ensemble E d'événements
 Coupure C est un sous-ensemble fini de E tel que
 Soit a et b deux événements du même processus :
a ∈ C et b → a ⇒ b ∈ C
 Si un événement d'un processus appartient à la coupure, alors tous
les événements locaux le précédant y appartiennent également
 Etat associé à une coupure
 Si le système est composé de N processus, l'état associé à une
coupure est défini au niveau d'un ensemble de N événements
(e1, e2, ... ei, ... eN), avec ei événement du processus Pi tel que
 ∀i :∀e ∈ C et e événement du processus Pi ⇒ e → ei
 L'état est défini à la frontière de la coupure : l'événement le
plus récent pour chaque processus
36
 Coupure
 Exemple de coupure
(même chronogramme que pour exemples horloges Lamport et Mattern)

 Coupure = ensemble { e11, e12, e13, e21, e22, e23, e31, e32, e33, e34 }
 État défini par la coupure = (e13, e23, e34)
37
 Coupure/état cohérent
 Coupure cohérente
 Coupure qui respecte les dépendances causales des
événements du système
 Et pas seulement les dépendances causales locales à chaque
processus
 Soit a et b deux événements du système :
a ∈ C et b → a ⇒ b ∈ C
 Coupure cohérente : aucun message ne vient du futur

 État cohérent
 État associé à une coupure cohérente
 Permet par exemple une reprise sur faute
38
 Coupure cohérente
 Exemple (même chronogramme que précédent)

 Coupure C1 : cohérente
 Coupure C2 : non cohérente car e35 → e23 mais e35 ∉ C2
 La réception de m5 est dans la coupure mais pas son émission
 m5 vient du futur par rapport à la coupure
39
 Datation Coupure
 Horloge de Mattern permet de dater la coupure
 Soit N processus, C la 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), ... , V(eN) ) :
∀i : V(C)[ i ] = max ( V(e1)[ i ] , ... , V(eN)[ i ] )
 Pour chaque valeur du vecteur, on prend le maximum des valeurs
de tous les vecteurs des N événements pour le même indice
 Permet également de déterminer si la coupure est cohérente
 Cohérent si V(C) = ( V(e1)[ 1 ], ... , V(ei)[ i ], ... , V(eN) [ N ] )
 Pour un processus Pi, si l'événement ei est le plus récent c'est lui qui a la
date la plus récente pour C : sinon un événement ej d'un processus Pj
(i ≠ j) s'est déroulé après un événement ei' de Pi avec ei' plus récent que ei
 ei → ei' et ei' → ej avec ei ∈ C, ej ∈ C et ei' ∉ C
40
 Datation Coupure
 Datation des coupures de l'exemple
 Coupure C1 : état = (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)
 Coupure cohérente car V(C)[1] = V(e13)[1], V(C)[2] = V(e22)[2],
V(C)[3] = V(e33)[3]
 Coupure C2 : état = (e13, e23, e34)
 V(e13) = (3,0,0), V(e23) = (2,3,5), V(e34) = (2,0,4)
 V(C) = (max(3,2,2), max(0,3,0), max (0,5,4))
 Non cohérent car V(C)[3] ≠ V(e34)[3]
 D'après la date de e23, e23 doit se dérouler après 5 événements de
P3 or e34 n'est que le quatrième événement de P3
 Un événement de P3 dont e23 dépend causalement n'est donc pas
dans la coupure (il s'agit de e35 se déroulant dans le futur).
41
 Détermination état cohérent
 Algorithme de Chandy & Lamport, 1985
 Algorithme permettant aux processus distribués
d'enregistrer un état global cohérent
 Principe général
 Un processus diffuse un événement marqueur et les
processus enregistrent leur état
 Fonctionnement asynchrone
 Contraintes sur le système
 Canaux de communication uni-directionnels et FIFO
 Fiable : pas de plantage ou de perte de message
 Topologie de connexion fortement (voire totalement) connexe
 Pour faciliter la diffusion
42
 Détermination état cohérent
 État d'un canal
 Pour un canal FIFO fiable unidirectionnel
 Canal pour envoi de message du processus Pi vers Pj
 A un instant t, l'état du canal < i, j > est l'ensemble
des messages émis par Pi et non encore reçus par Pj
 Pour le chronogramme de l'exemple, états des
canaux par rapport à la coupure C1
 Événements de la frontière de la coupure : e13 pour P1 et e33 pour P3
 État du canal < 1, 3 > = { m3 }
 m3 a été envoyé en e12 et ne sera reçu qu'en e34
 État du canal < 3, 1 > = { m4 }
 m4 a été envoyé en e33 et ne sera reçu qu'en e14

43
 Algorithme de Chandy & Lamport
 Fonctionnement algorithme Chandy & Lamport
 Un processus Pk est initiateur du lancement de l'algo

Il enregistre son état local

Il envoie un message marqueur à tous les processus
 Un processus Pj, à la réception du marqueur sur son canal < k, j >
 Enregistre son état local (données, variables ...)
 Positionne l'état de chacun de ses canaux entrants < i, j > à vide
S’il reçoit la première fois le marqueur
 Envoie un marqueur sur tous ses canaux sortants : à tous ses voisins
 Ces 3 étapes sont exécutées en une séquence atomique
 Pour un processus Pj, à la réception du marqueur venant de
Pi, sur le canal entrant < i, j >
 Enregistre l'état du canal < i, j > : tous les messages reçus sur
< i, j > depuis la réception du premier marqueur venant de Pk
44
 Algorithme de Chandy & Lamport
 Fonctionnement algorithme Chandy & Lamport (fin)
 Pour un processus Pj, l'algorithme est fini quand il a reçu
un marqueur sur chacun de ses canaux
 L'état enregistré pour Pj est composé de
 Son état local (variable, données ...)
 Les états de tous ses canaux entrants
 Pour constituer l'état global
 On collecte l'ensemble des états enregistrés par les
processus
 Une fois que l'on sait que tous les processus l'ont
enregistrés
45
 Algorithme de Chandy & Lamport
 Principe du double marqueur pour savoir quand tout le
monde a enregistré son état local
 Le premier marqueur vient du processus initiateur
 Le processus Pi « s'arrête » alors (ou passe dans une autre
phase de son calcul)
 Il précise à tous ses voisins qu'il s'est arrêté en leur envoyant un
marqueur
 Il se met en attente de messages l'informant que ses processus
voisins se sont arrêtés également
 A la réception d'un marqueur sur un canal, on sait qu'un
de ses voisins s'est arrêté
 Et que tous ses voisins se sont arrêtés quand on a reçu un
marqueur sur tous ses canaux
 Quand tout le monde est au courant de l'arrêt de tout le
monde : c'est fini
46
 Algorithme de Chandy & Lamport
 Intérêt d'enregistrer les messages sur < i, j >
 Les processus ne sont pas synchronisés et les temps de
propagation des messages sont non nuls
 Ne sait donc pas quand un processus s'arrête et si tous
les messages qu'il a envoyé ont été reçus quand il le fait
 Donc doit enregistrer les messages venant de Pi
 Comme les canaux sont FIFO, si on reçoit le marqueur de Pi, on
sait que tous les messages envoyés par Pi sont maintenus reçus,
plus aucun n'est en transit

47
 Algorithme de Chandy & Lamport
 Propriété de l'état global enregistré
 Correspond à un état cohérent
 L'algorithme définit une coupure
 Frontière est formée pour chaque processus par l'événement
d'enregistrement de l'état local et de diffusion du marqueur aux
autres processus (via une séquence atomique)
 Cette coupure est cohérente
 Car canaux FIFO : aucun message ne peut en doubler un autre
 Localement pour un processus Pj, si un marqueur est reçu sur un canal
< i,j >, cela implique qu'aucun message émis par Pi et reçu par Pj avant le
marqueur n'a pu être émis après que Pi émette son marqueur
 Pas de message venant du futur
 Pour un processus Pj, les événements d'émission des messages en transit
(à destination d'autres processus) « coupant » la coupure ont forcément
lieu avant son événement local définissant la frontière
48
 Algorithme de Chandy & Lamport
 Exemple avec 3 processus totalement interconnectés

 eM : événement d'enregistrement d'état et diffusion marqueur

 eF : événement où l'état local complet est enregistré
 États canaux : <3,1> = { m3, m4 }, <2,3> = { m5 }, autres sont vide

49