Gestion du temps et des états dans les systèmes distribués

2 Propri´et´e de causalit´e ´el´ementaire: a→b si a et b sont

respectivement les ´ev`enements d’envoi et de r´eception d’un

mˆeme message.

3 Transitivit´e: si a→b et b→c alors a→c

L’ordre local est facilement ´etabli en utilisant une horloge ou

un compteur (a incr´ementer a l’occurrence des ´ev`enements)

La relation de pr´ec´edence causale est une relation d’ordre

partiel : il est possible d’avoir deux ´evenements impossibles a

classer par cette relation d’ordre : ´ev`enements concurrents.

Syst`emes Distribu´es (FSB 2009)

K. Barbaria

7/27

Gestion du temps et des ´etats dans les syst`emes distribu´es

Ordre causal (2)

Classer causalement les diff´erents ´ev`enements ayant lieu sur

les sites S1, S2 et S3.

Quels sont les ´ev`enements concurrents? (distinguer la

concurrence physique de la concurrence logique (ou causale).

e11 e12

e13

e14

e15

e21

e22 e23

e24

e25

e31

e32

e33

e34

S1

S2

S3

Syst`emes Distribu´es (FSB 2009)

K. Barbaria

8/27

Gestion du temps et des ´etats dans les syst`emes distribu´es

Ordre causal (3)

Si deux ´evenements se pr´ecedent causalement alors ils se

pr´ec`edent r´eellement (ordre ´etabli par un observateur r´eel,

externe au syst`eme). L’inverse n’est pas vrai. Deux

´evenements qui se pr´ecedent r´eellement peuvent ne pas ˆetres

class´es par la relation d’ordre causal (´ev`enements

concurrents).

Concurrence logique : pas de causalit´e

Concurrence physique : occurrence en mˆeme temps physique.

Deux ´ev`enements peuvent ˆetre concurrents logiquement

mˆeme s’ils ne sont pas concurrents physiquement.

Si deux ´ev`enements sont en concurrence logique, l’ordre de

leurs ex´ecutions (avant, apr`es, en mˆeme temps) ne change pas

le r´esultat des interactions entre les processus.

Syst`emes Distribu´es (FSB 2009)

K. Barbaria

9/27

Gestion du temps et des ´etats dans les syst`emes distribu´es

Ordonnancement des ´ev`enements distribu´es

La relation de pr´ec´edente causale est fondamentale. Si tous

les processus peuvent avoir le mˆeme ordre sur les ´ev`enements

qui les int´eressent ils pourront interagir sans conflits.

Pour ´etablir un ordre sur les ´ev`enements, on leurs associe des

dates en utilisant des horloges.

Propri´et´es des horloges :

Monotonie : l’horloge doit toujours avancer (s’il y a des

corrections, il faut les appliquer en incr´ementant l’horloge.

Deux ´ev`enements diff´erents ne doivent pas avoir la mˆeme date.

Coh´erence : Si a → b alors H(a) < H(b)

Syst`emes Distribu´es (FSB 2009)

K. Barbaria

10/27

Gestion du temps et des ´etats dans les syst`emes distribu´es

Horloges logiques

La relation de pr´ec´edence causale permet aux processus de

distinguer les ´evenements concurrents des ´evenements qu’ils

doivent trait´es dans l’ordre.

Il faut donner le moyen aux processus de d´ecider de cette

d´ependance causale. Id´ealement, il faut donner `a chaque

processus le moyne d’´etablir un ordre total sur tous les

´evenements du systeme.

Il est possible pour un processus d’´etablir un tel ordre en se

basant uniquement sur des informations consultables

localement. Les horloges logiques permettent d’avoir cet

ordre.

Syst`emes Distribu´es (FSB 2009)

K. Barbaria

11/27

Gestion du temps et des ´etats dans les syst`emes distribu´es

Algorithme de l’horloge logique (de Lamport)

Objectif : R´ealiser une datation des ´ev`enements compatible

avec la causalit´e et d´efinissant un ordre total sur les

´ev`enements.

Algorithme : chaque site Si maintient une variable Hi .

Initialisation : Hi ← 0 ∀i

1

2 A chaque ´ev`enement local sur Si : Hi ← Hi +1;

3 ´Emission d’un message : ´ev`enement local, cause une

incr´ementation de Hi . Le message est estampill´e par la date de

son ´emission. ∀m message : H(m) ← H(´emission(m))

4 R´eception d’un message m : Hi ← max (Hi ,H(m)) +1;

Syst`emes Distribu´es (FSB 2009)

K. Barbaria

12/27

Gestion du temps et des ´etats dans les syst`emes distribu´es

Exemple d’application

S1

e11 e12

e13

e14

e15

1

2

3

4

5

S2

e21

1

e22

e23

e24

e25

3

4

5

6

S3

e31

1

e32

5

e33

e34

6

7

Syst`emes Distribu´es (FSB 2009)

K. Barbaria

13/27

Gestion du temps et des ´etats dans les syst`emes distribu´es

Ordre d´efini par les horloges logiques

Soient deux ´ev`enements a et b, H(a) et H(b) d´esignent leurs

dates respectives. L’ordre d´efini par les horloges de Lamport

est not´e “<<”. a<<b (a pr´ec`ede b) si

H(a)<H(b)

H(a)=H(b) et le site de a est plus petit que le site de b.

L’ordre ainsi d´efini est total : il est possible d’ordonner tous

les ´evenements du systeme.

Sur l’exemple cela donne :

e11 << e21 << e31 << e12 << e13 << e22 << e14 <<

e23 << e15 << e24 << e32 << e25 << e33 << e34

Application : exclusion mutuelle, multicast totalement

ordonn´e et r´eplication.

Limites : i. la comparaison des dates des horloges ne permet

pas de dire si un ´ev`enement a eu lieu avant l’autre

(H(a) < H(b) ; a → b . ii. les horloges ne sont pas born´ees.

Syst`emes Distribu´es (FSB 2009)

K. Barbaria

14/27

Gestion du temps et des ´etats dans les syst`emes distribu´es

Horloges vectorielles

Objectif : On suppose que les sites sont class´es de 1 `a n.

Algorithme : Chaque site Si maintient un vecteur Vi de

taille n.

Initialisation : Vi = (0,. . . ,0)

A chaque ´ev`enement local sur Si : Vi [i] ← Vi [i]+1

´Emission d’un message : Vi [i] ← Vi [i]+1. Le message est

estampill´e par la date de son ´emission. ∀m message :

V (m) ← V (emission(m))

R´eception d’un message m : Vi [i] ← Vi [i]+1 et

Vi [j] ← max(V (m)[j], Vi [j])∀i 6= j

Syst`emes Distribu´es (FSB 2009)

K. Barbaria

15/27

Gestion du temps et des ´etats dans les syst`emes distribu´es

Exemple d’application

S1

000

S2

000

S3

00 0

e11

e12

e13

001

002

003

e14

004

e15

005

e21

001

e22

022

e23

023

e24

e25

024

045

e31

0 10

e32

232

e33

e34

243

442

Syst`emes Distribu´es (FSB 2009)

K. Barbaria

16/27

Gestion du temps et des ´etats dans les syst`emes distribu´es

Ordre d´efini par les horloges vectorielles

Relation d’ordre sur les horloges vectorielles

V ≤ V ′ ssi ∀i V [i] ≤ V ′[i]

V < V ′ ssi V ≤ V ′ et ∃i; V [i] 6= V ′[i]

V ||V ′ ssi non (V < V ′) et non (V ′ < V )

Les horloges vectorielles repr´esentent exactement la

d´ependance causale : ∀a, b evts

a → b ⇔ Va < Vb

a||b ⇔ Va||Vb

Les horloges vectorielles ne d´efinissent pas un ordre total.

Les horloges vectorielles comptent le nombre d’´ev`enements

qui pr´ecedent un ´evenement donn´e sur l’ensemble des sites. Si

Ve[i ] = m, il y a m ´evenements qui pr´ecedent e sur le site Si

Syst`emes Distribu´es (FSB 2009)

K. Barbaria

17/27

Gestion du temps et des ´etats dans les syst`emes distribu´es

Applications et limites

Applications :

D´eterminent tous les ´ev`enements concurrents

Multicast causalement ordonn´e.

V´erification de la coh´erence de points de reprise.

Limites :

Les vecteurs doivent ˆetre transport´es avec tous les messages.

Probleme de passage a l’´echelle si le nombre de processus est

grand.

Les horloges ne sont pas born´ees.

Syst`emes Distribu´es (FSB 2009)

K. Barbaria

18/27

Gestion du temps et des ´etats dans les syst`emes distribu´es

Etat global d’un SD : exemple introductif

S1

S2

S3

S1

S2

S3

c21

t1

1

0

0

0

t2

0

0

0

1

t3

0

1

0

0

Un jeton circule entre S1, S2 et S3 (message en pointill´e). A

tout instant le jeton est soit au niveau de l’un des sites soit en

transit (dans l’un des canaux des communications)

S3 veut savoir combien de jetons existent dans le syst`eme

(messages en rouge). Qu’aura t-il en r´eponse?. Est t-il

possible d’avoir d’autres r´eponses?

Syst`emes Distribu´es (FSB 2009)

K. Barbaria

19/27

Gestion du temps et des ´etats dans les syst`emes distribu´es

Etat global d’un SD : exemple introductif

S1

S2

S3

S3 aura l’impression qu’il y a deux jetons qui circulent.

C’est une vision incorrecte de l’´etat global du syst`eme.

Le probl`eme de construire une vision coh´erente de l’´etat

global d’un syst`eme distibu´e est difficile.

Il est impossible d’avoir une vision simultan´ee des ´etats des

autres processus et des diff´erents canaux de communications.

Il faut donc construire une vision de l’´etat global `a partir de

visions prises `a des instants diff´erents mais qui rend une

information utile et coh´erente sur le syst`eme. Cette vision ne

doit en aucun cas contredire la r´ealit´e.

Syst`emes Distribu´es (FSB 2009)

K. Barbaria

20/27

Gestion du temps et des ´etats dans les syst`emes distribu´es

Etat global d’un SD

Chaque processus Si poss`ede un ´etat local eli . cet ´etat r´esulte

de son ´etat initial et de la s´equence des ´ev`enements ayant lieu

sur le site.

Chaque canal de communication cij (entre Si et Sj ) admet

pour ´etat ecij l’ensemble des messages en transit (´emis par Si

et pas encore re¸cus par Sj )

Actions influant sur l’´etat global :

Evenement interne a un site Si : changement de eli

Envoi d’un message m de Si vers Sj : cij ← cij ∪ m

R´eception d’un message m envoy´e de Sj vers Si : cij ← cij − m

L’´etat global du syst`eme est donn´e par [

i

eli + [

i ,j

ecij

Syst`emes Distribu´es (FSB 2009)

K. Barbaria

21/27

Gestion du temps et des ´etats dans les syst`emes distribu´es

Etat global coh´erent

Un ´etat global coh´erent est un global compatible avec le

principe de causalit´e.

Si l’emission d’un message est capt´e dans eli alors soit sa

r´eception est capt´ee dans elj , soit il appartient `a cij

Si l’emission de m n’est pas capt´ee dans eli alors sa r´eception

n’est pas capt´ee dans elj

Un ´etat global coh´erent corrspond `a une coupure coh´erente

Syst`emes Distribu´es (FSB 2009)

K. Barbaria

22/27

Gestion du temps et des ´etats dans les syst`emes distribu´es

Etat global et coupure

Coupure

Une coupure est un ensemble d’´ev`enements contenant au moins un

´ev`eenemement par site.

Coupure coh´erente

Une coupure est dite coh´erente si elle est ferm´ee par la relation de

d´ependance causale. Soit C une couptre , a et b deux evts. C est

coh´erente ssi : (a ∈ C et a → b) ⇒ b ∈ C

S1

S2

S3

S1

S2

S3

(a) pas coh´erente

(b) coh´erente

Syst`emes Distribu´es (FSB 2009)

K. Barbaria

23/27

Gestion du temps et des ´etats dans les syst`emes distribu´es

Date d’une coupure

Date d’une coupure

On appelle date de la coupure C = (c1, ..., cn) le vecteur d´efini par

V(C) = sup(V (c1), ..., V (cn)), V (ci ) ´etant l’horloge vectorielle

associ´ee `a ci .

100 200

300

010

220

230

240

S1

S2

S3

001

222

243

100 200

300

010

220

230

240

001

232

233

S1

S2

S3

(c) pas coh´erente

(d) coh´erente

V (Cc )=sup([3,0,0];[2,3,0];[2,4,3])=[3,4,3]

V (Cd )=sup([3,0,0];[2,4,0];[2,3,2])=[3,4,2]

Syst`emes Distribu´es (FSB 2009)

K. Barbaria

24/27

Gestion du temps et des ´etats dans les syst`emes distribu´es

Condition de coh´erence d’une coupure

Condition de coh´erence d’une coupure

Une coupure C = (c1, ..., cn) est coh´erente ssi

V (C ) = sup(V (c1), ..., V (cn)) = (Vc1[1] . . . Vci [i ] . . . Vcn[n])

Pour la coupure d : (Vc1[1] . . . Vci [i ] . . . Vcn[n])=[3,4,2]. Elle

est donc coh´erente!

Pour la coupure c : (Vc1[1] . . . Vci [i ] . . . Vcn[n])=[3,3,3]. Elle

n’est pas coh´erente. Le vecteur nous indique d’o`u vient le

probleme : un ´evenement sur le site 2.

Syst`emes Distribu´es (FSB 2009)

K. Barbaria

25/27

Gestion du temps et des ´etats dans les syst`emes distribu´es

Algorithme de Chandy-Lamport

Algorithme de Chandy-Lamport

Envoi d’un marqueur par Si :

1 Si enregistre son ´etat

2 Pour chaque canal cix Si envoie le marqueur en utilisant ce

canal avant d’envoyer tout autre message.

R´eception d’un marqueur par Sj (par le canal cxj ):

1 Si Sj n’a pas encore enregistr´e son ´etat, il effectue un envoi de

marqueur comme d´ecrit ci dessus.

2 Sinon Sj met `a jour l’´etat du canal : ecxj ={messages re¸cus

par ce canal apr`es l’enregistrement de l’´etat de Sj et avant la

r´eception du marqueur}

Syst`emes Distribu´es (FSB 2009)

K. Barbaria

26/27

Gestion du temps et des ´etats dans les syst`emes distribu´es

Exemple d’application

S1

S2

S3

ec21

ec12

ec23

ec13

Le jeton est capt´e dans l’´etat du canal ec12

Reste une phase de construction de l’´etat global. Les

informations ´echangent `a leurs ´etats locaux (dont la coh´erence

est assur´ee) ainsi que les ´etats des canaux qu’ils ont eregistr´es.

Syst`emes Distribu´es (FSB 2009)

K. Barbaria

27/27