Chapitre 2

Synchronisation
 Préliminaires(1/4)
30

 Processus
 On note P1, P2, ... Pn les processus du système distribué (il s’agit

juste d’un élément du système, qui peut être une machine entière

contenant plusieurs applications que réalisent le processus).

 Ces processus communiquent à travers l’échange de messages.

 Nous supposons qu’il y a forcément un délai entre l’émission d’un

message et sa réception.

 Chaque processus avance à sa propre vitesse, qui n’est pas

identique pour tous les processus.

 Préliminaires(2/4)
31

 Message
 Chaque message m M est envoyé sur un réseau asynchrone,
fiable et ayant les caractéristiques suivantes :
 temps de transmission fini,
 aucun ordre de transmission et
 pas de perte de messages.
 Nous supposerons que le réseau de communication est fiable : les
messages arrivent toujours, et ils arrivent intacts.
 Les communications étant asynchrones, nous n’avons pas de limite
sur le temps de transit d’un message.
 Préliminaires(3/4)
32

 Evénement
 Il existe deux types d'événement : événement interne et événement externe.
 Un événement interne : est une action unique qui peut avoir lieu
dans un processus d'une manière locale et qui change l'état local
de ce processus.
 Un événement externe : est une action unique qui peut avoir lieu
dans un processus, qui peut être vue par les autres processus en
communication et qui change l'état global du système. Les
événements externes considérés sont les événements d'émission et
les événements de réception.
 Préliminaires(4/4)
33

 Trois types d’événements peuvent se produire durant le

cycle de vie d’un processus :
 Événement interne (ou local) dans l'évolution du processus
 Événement d’émission d'un message d’un processus à
destination d'un autre.
 Événement de réception d'un message provenant d'un autre
processus
 Chronogramme(1/3)
34

 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
 Réception d'un message
 Événement local
 Les messages échangés doivent respecter la topologie de
liaison des processus via les canaux.
 Chronogramme(2/3)
35

 Exemple :
 Soit un système distribué composé de trois processus P1,
P2 et P3.
p1 e11 e12 e13 e14 e15 e16 e17
m1
m4 m7 m6
p2
e21 e22 e23 e24 e25 e26 e27
m8
m5
p3
e31 e32 e33 e34 e35 e36 e37
 Chronogramme(3/3)
36

 Pour P1
 e11 : événement d'émission du message m1 vers le processus P2
 e13 : événement local au processus
 e14 : réception du message m4 provenant du processus P2
 Pour P2 : message m6 envoyé avant m7 mais m7 reçu avant m6
 Pour P3 : le message m8 est perdu par le canal de communication
 Comment numéroter un événement ?
 Nous notons un événement par :
exy
x : Numéro du processus et y : Numéro de l'événement pour le processus
 Causalité dans les systèmes distribués(1/4)
37

 Relation binaire
Considérons un ensemble A d’objets non vide, si nous associons à cet
ensemble des outils permettant de comparer les éléments le composant
alors nous parlons de relation binaire ou de comparaison R :
(x, y) A : xRy

 Relation d’ordre
Une relation binaire R, définie sur un ensemble A, est dite relation d’ordre
si elle est réflexive, antisymétrique et transitive.
 Causalité dans les systèmes distribués(2/4)
38

Définition 1
Soit un ensemble A d'au moins trois éléments x, y et z et une
relation binaire R définie sur A. R est une relation d'ordre si elle
possède les propriétés suivantes :
• antisymétrie : pour tout x et pour tout y de A, x ≠y, xRy => y
¬R x.
• transitivité : pour tout x, y, z de A, (xRy) et (yRz) => xRz.
• réflexivité : x A, xRx.
 Causalité dans les systèmes distribués(3/4)
39

 Relation d’ordre strict

Si R est antisymétrique, transitive et antiréflexive, alors nous parlons de relation
d’ordre strict.

 Relation d’ordre strict total

Un ordre total est une relation d'ordre R telle que pour tout couple (x, y)
d'éléments distincts de A :
xRy ou yRx
 Relation d’ordre strict partiel
Un ordre partiel est une relation d'ordre R telle qu'il existe un couple (x, y)
d'éléments distincts de A tel que :
x ¬R y et y ¬R x
 Causalité dans les systèmes distribués(4/4)
40

 Ordre des événements locaux à un site

 On peut définir un ordre strict total sur les événements
locaux à un site
 Ordre des événements distants
 Les délais de transmission des messages sont variables
 L’état d’un site est perçu par les autres sites uniquement à
travers les informations véhiculées par les messages
 Deux sites distincts peuvent avoir une vision différente de l’état
d’un troisième site.
 Dépendance causale(1/7)
41

 Relation de dépendance causale

 Une dépendance causale existe entre 2 événements si
un événement doit avoir lieu avant l'autre.
 La relation arrivé-avant, connue par HBR (Happened-

Before Relation), est définie par Lamport. Cette

relation établit les dépendances de priorité causale

dans un ensemble d'événements.

 Dépendance causale(2/7)
42

 HBR est définie comme suit :

Définition 2 La relation causale "→" est une relation vérifiant
les conditions suivantes :
1. Si a et b deux événements qui appartiennent au même
processus et a est arrivé avant b alors a → b.
2. Si a et b appartiennent à deux processus différents et a est
l'événement d'émission d'un message m par P et b est l'événement
de réception de ce message par Q alors a → b.
3. Si a → b et b → c alors a → c.
 Dépendance causale(3/7)
43

 Exemple

p1 e11 e12 e13 e14 e15 e16 e17

m1
m4 m7 m6
m3
p2
e21 e22 e23 e24 e25 e26 e27
m2 m5
p3
e31 e32 e33 e34 e35 e36 e37
 Dépendance causale(4/7)
44

 Quelques dépendances causales autour de e12

 Localement : e11  e12, e12  e13
 Sur message : e32  e12
 Par transitivité :
 e32  e13 car (e32  e12) et (e12  e13)

 Dépendance causale entre e13 et e33 ?

 A priori non : absence de dépendance causale
 Des événements non liés causalement se déroulent en
parallèle.
 Dépendance causale(5/7)
45

 Ordonnancement des événements

 Les dépendances causales définissent un ordre strict
partiel pour les ensembles d'événements du système.

 Puisqu’on ne peut pas établir un ordre entre e13 et e33

 Uniquement les événements dépendants causalement

qui peuvent participer à cet ordre strict.
 Dépendance causale(6/7)
46

 Relation de concurrence : ||
 e || e' équivalent à ¬((e  e') v (e'  e)) : e et e’ sont concurrents
 Aucun des deux événements n’appartient au passé de l’autre
 Aucun des deux événements ne peut influer sur l’autre

 Les 2 événements peuvent se dérouler simultanément comme il

peuvent se dérouler dans n'importe quel ordre (Concurrence
logique)
 e13 et e33 sont concurrents puisque ¬(e13  e33) et ¬(e33  e13)
 Dépendance causale(7/7)
47

 Conséquences : à tout évènement e, on peut

associer 3 ensembles d'évènements :
 Passé (e) : causalement antérieurs à e
 Futur (e) : causalement postérieurs à e
 Concurrent(e) : évènements concurrents à e
 Temps logique dans un système distribué
48

 Définir un temps global cohérent et identique pour

tous les processus :
 N'est pas lié à un temps physique
 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ée un ordonnancement
logique
 Horloges et estampilles scalaires (1/5)
49

 Chaque site gère un compteur dont la valeur est un entier.

 Sur chaque site ce compteur est initialisé à 0 au démarrage.
 La valeur de l’horloge logique d’un site est incrémentée
chaque fois qu’un événement local s’y produit. Un tel
événement est :
 soit une opération purement locale,
 soit l’envoi d’un message : dans ce cas la valeur courante
(après incrémentation) de l’horloge de l’émetteur est
embarquée avec le message «piggybacking» et sert à
l’estampiller.
 Horloges et estampilles scalaires (2/5)
50

 La réception d’un message permet de synchroniser

l’horloge du récepteur avec celle de l’émetteur du
message (qui est transportée par le message).
 Le principe consiste à attribuer à l’horloge du récepteur
une valeur supérieure à la fois à la valeur courante de
l’horloge du site et à celle de l’estampille du message
reçu.
 Horloges et estampilles scalaires (3/5)
51

 En résumé
 HLi désigne l’horloge logique du site i et Elm désigne l’estampille
logique attribuée au message m lors de son envoi :
 si un événement local se produit sur le site i, HLi est incrémentée :
HLi ++
 si un événement correspondant à l’envoi d’un message se produit sur
le site i, HLi est incrémentée, et le message m est envoyé avec la
nouvelle valeur de HLi comme estampille : ELm = HLi
 si un événement correspondant à la réception d’un message m
d’estampille ELm se produit sur le site i : HLi = max (HLi , ELm) + 1
 Horloges et estampilles scalaires (4/5)
52

 Exemple :
 Donner les valeurs des horloges des événements suivants :
 Horloges et estampilles scalaires (5/5)
53

 Ordre strict sur les estampilles

 Deux événements indépendants causalement se produisant
sur des sites distincts peuvent avoir la même date.
 Pour avoir un ordre strict sur les estampilles, il suffit de
définir un ordre arbitraire sur les sites.
 soient A et B deux événements se produisant respectivement
sur les sites Si et Sj et estampillés par (i,Ha) et (j,Hb)
(A<<B)  (Ha<Hb) ou ((Ha=Hb) et (i<j))
Il s’agit d’une relation d’ordre strict total
 Horloges logiques
54

 Dater les événements d’un système distribué en respectant les

dépendances causales entre ces événements. Trois familles
d'horloge :
 Horloge de Lamport (1978)
 Une donnée par événement : information au niveau global
 Horloge de Mattern (1988)
 Un vecteur par événement : information sur chacun des autres processus
 Horloge Matricielle
 Une matrice par événement : Contenant le nombre des événement
locaux, d’émission et de réception pour chaque processus.
 Horloge de Lamport (1/8)
55

 Une date est associée à

chaque événement :

couple (P, HP)

P : numéro HP : valeur
du processus de l’horloge
 Horloge de Lamport (2/8)
56

 Création du temps logique

 Pour dater les événements, chaque processus P possède
une horloge locale logique Hp, initialisée à 0
 Pour chaque événement local de P
 On incrémente l'horloge locale (Hp = Hp + 1)
 Émission d'un message par P
 On incrémente Hp de 1 (Hp = Hp + 1)
 ELm= Hp
 On envoie le message avec (P, ELm) comme estampille
 Horloge de Lamport (3/8)
57

 Réception, par P, d'un message m avec estampille

(Q, ELm)
 Hp = max(Hp, ELm) +1
 Marque l'événement de réception avec Hp
 Hi est éventuellement
 recalée sur l'horloge de l'autre processus par l’action
[max(Hp, ELm)]
 puis incrémentée par l’action [+1]
 Horloge de Lamport (4/8)
58

 Exemple :
 Donner les valeurs des horloges des événements suivants :
 Horloge de Lamport (5/8)
59

 Respect de la dépendance causale

 Soient deux événements :
epavec H(ep)=(p,HP) et eq avec H(eq)= (q,Hq)
 e p eq signifie H(ep) < H(eq)
 ep || eq signifie (HP < Hq) ou (HP = Hq et p < q)

 Mais pas la réciproque :

 H(ep) < H(eq) signifie (ep eq) OU ¬ (ep eq)
 C'est-à-dire : soit ep eq soit ep||eq
 Horloge de Lamport (6/8)
60

 Ordonnancement global
 Via la valeur de l’horloge, on ordonne tous les
événements du système entre eux.
 Ordre total obtenu est arbitraire
 Si les deux événements sont dépendants causalement :
L’ordre respecte cette dépendance.
 Si les deux événements sont indépendants causalement :
choix d'un ordre entre les 2
 Horloge de Lamport (7/8)
61

 Ordre total
 Un ordre strict total est établi entre tous les événements
du système à l’aide de l’opérateur [<<]
ep << eq : signifie que ep s'est déroulé avant eq

 Si les deux événements sont générés sur le même

processus : la valeur de l’horloge donne l'ordre des
événements du processus
 Horloge de Lamport (8/8)
62

 Soit ep événement de P et eq événement de Q :

ep << eq  ((HP < Hq )V (HP = Hq et p < q)
 Les deux horloges de deux processus différents
permettent de déterminer l'ordonnancement des
événements
 Si égalité de la valeur de l'horloge, le numéro du
processus est utilisé pour les ordonner
 Constat
63

 Les estampilles définissent un ordre strict total

 La dépendance causale est une relation d’ordre strict partiel
 Les estampilles effacent artificiellement la notion de
dépendance causale
 ep << eq alors ep  eq ou ep et eq sont concurrents

 Les estampilles ne sont pas denses

 si H(ep) < H(eq) , on ne peut pas savoir s’il existe e ’ ’ tq
ep  e ’ ’ et e ’ ’  eq

 Les estampilles ne garantissent pas la réciprocité

ep  eq  H(ep) < H(eq)
 Horloge de Mattern (1/5)
64

 Horloge de Mattern & Fidge,

1989-91
 Utilisation de vecteur V de taille
égale au nombre de processus
 Localement, chaque processus P
a un vecteur Vp
 Un message est envoyé avec un
vecteur de date
 Pour chaque processus P, chaque
case Vp[p] du vecteur
contiendra des valeurs de
l'horloge du processus P
 Horloge de Mattern (2/5)
65

 Création du temps logique

 Initialisation : pour chaque processus P, Vp =(0, ... , 0)
 Pour un processus P, à chacun de ses événements (local,
émission, réception) :
 Incrémentation de l’horloge de p : Vp [p] = Vp [p] + 1
 Si émission d'un message : ELm =Vp et le message est envoyé
avec Elm
 A la réception d'un message m par le processus P contenant
Elm :
 Vp[j] = max(ELm[j], Vp [j]); Pour j de 1 à N\{p}
 Horloge de Mattern (3/5)
66

 Exemple
 Donner les valeurs des horloges des événements suivants :
 Horloge de Mattern (4/5)
67

 Relation d'ordre partiel sur les dates

 Si i : V[ i ] ≤ V'[ i ] alors
 V ≤ V’
 Si V ≤ V' et j tel que V [ j ] < V' [ j ] alors
V < V’
 Si ¬( V < V' ) ¬( V' < V ) alors
V || V'
 Horloge de Mattern (5/5)
68

 Dépendance et indépendance causales

 ep et eq deux événements et V(ep) et V(eq) leurs datations.
L’horloge de Mattern assure les propriétés suivantes :
 Si deux dates sont ordonnées, on a forcément dépendance
causale entre les deux événements
V(ep) < V(eq) ep → eq
 Si aucun ordre entre les deux dates ne peut être établi, les deux
événements sont indépendants causalement
V(ep) || V(eq) ep || eq
 Constat
69

Horloge de Mattern Horloge de Lamport

- L'horloge de Mattern respecte les - L’horloge de Lamport respecte

dépendances causales des cela également
événements
- L'horloge de Mattern respecte les - L'horloge de Lamport impose un
indépendances causales ordre arbitraire entre les
événements indépendants
causalement
 Horloge matricielle (1/4)
70

 Pour le dater, on associe à chaque événement une matrice M

de (n x n) où n est le nombre de processus dans un système
distribué
 Matrice Mp pour le processus P
 Ligne p : informations sur événements de P
 Mp [p, p ] : nombre d'événements réalisés par P
 Mp [ p , q ] : nombre de messages envoyés par P à Q (avec p ≠ q)
 Ligne q (avec q ≠ p)
 Mp [ q , k ] : nombre de messages que l'on sait que Q a envoyé à K
 Mp [ q , q ] : nombre d'événements que l'on connait sur Q (avec q ≠ k)
 Horloge matricielle (2/4)
71

 Création de l’horloge logique

 Evénement local à P :
 HMp[p,p]←HMp[p,p]+1

 Emission du message m de P vers Q

 HMp[p,p]←HMp[p,p]+1

 HMp[p,q]←HMp[p,q]+1

 Le message m est estampillé Elm=HMp

 Horloge matricielle (3/4)
72

 Réception de (m, ELm) en provenance du processus Q

 La matrice HMp et ELm sont disponibles pour assurer la
délivrance
 Le message m ne peut être délivré qu’après avoir délivré
tous les messages antérieurs :
 Respect de l’ordre FIFO sur le canal Q→P :
ELm[q,p]= HMp[q,p]
 Respect de l’ordre de réception :
ELm[k,p]= HMp[k,p], k ≠p
 Horloge matricielle (4/4)
73

 Lors de la délivrance du message (m, ELm) en

provenance de Q, mettre à jour l’horloge
 HMp[p,p]← HMp[p,p] + 1

 HMp[p,q]← HMp[p,q] + 1

 HMp[k,l]←max(HMp[k,l], ELm[k,l]) pour tout k ≠ p, pour tout l

≠p
 Etat Global
74

 État du système et de ses composants à un instant donné

 Pourquoi on cherche des états globaux
 Trouver des états cohérents à partir desquels on peut reprendre
un calcul distribué lorsque le système tombe en panne.
 Faciliter le debugging et la mise au point d'applications
distribuées
 Un état global est défini à l’aide de coupure
 Une coupure est une photographie à un instant donné de l'état
du système
 Coupure
75

 Détermine les événements appartenant au passé et au futur

par rapport à l'instant de la coupure
 Soit E l’ensemble des événements réalisés pour un système
distribué. Coupure C est un sous-ensemble fini de E tel que pour
deux événements a et b 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 qui le précèdent y appartiennent
également
 Coupure cohérente (1/3)
76

 Une coupure cohérente est une coupure qui respecte les

dépendances causales (locales, par message, par
transitivité) des événements du système.
 Soit a et b deux événements du système :
a C et b → a b C
 Aucun message ne vient du futur

 Un état cohérent est un état associé à une coupure

cohérente.
 Coupure cohérente (2/3)
77

 Pour le chronogramme suivant :

cohérente
C 11 incohérente
C 21 C 31
p1
1 2
m3
C 2 m1 C 2 C 32
p2
1 m2 2 m4
C 3 C 3 C 33
p3

C1 C2

 La coupure C1 n’est pas cohérente puisque le message m1 vient du futur.

 La coupure C2 est cohérente.

 Coupure cohérente (3/3)
78

 Pour le chronogramme suivant :

C2 incohérente

C1 cohérente

 C2 est incohérente car alors que

 Datation de la coupure (1/2)
79

 Pour dater une coupure, on va se servir de l’horloge de

Mattern
 Soit un système distribué composé de N processus,
 C la coupure, ep l'événement le plus récent pour le processus P
 V(ep) la datation de ep
 V(C) la datation de la coupure avec
V(C) = max (V(e1) , …, V(eN))
 Autrement dit
i : V(C)[ i ] = max ( V(e1)[i], … V(eN)[ i ] )
 Datation de la coupure (2/2)
80

 La datation de la coupure Permet aussi de

déterminer si la coupure est cohérente ou pas
 Si la coupure C est cohérente alors
V(C) = ( V(e1)[ 1 ], ... , V(ei )[ i ], ... , V(eN) [ N ] )