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

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

distribués

K. Barbaria

Faculté des Sciences de Bizerte

Octobre 2009

Systèmes Distribués (FSB 2009)

K. Barbaria

1/27

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

Introduction

2 Relation de causalité

3 Horloges logiques

4 Horloges vectorielles

5 Gestion des états

Systèmes Distribués (FSB 2009)

K. Barbaria

2/27

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

Introduction

La latence caractérise les systèmes distribués.

Les délais sont dûs au moyen de communications. Ces délais

sont significatifs et variables

Il est possible d’avoir des exécutions différentes d’un même

protocole (avec des résultats différents) à cause des variations

de délais

Exemple : un chef envoie un premier message pour demander

l’ouverture d’une vanne. Quelques minutes après, il envoie un

second message pour demander la fermeture.

Selon les délais de transfert, on peut avoir une quantité de

liquide variable.

Que se passe t’il si les message se dédoublent dans le canal de

transmission?!

Systèmes Distribués (FSB 2009)

K. Barbaria

3/27

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

Évenements dans un systeme distribué

Évènement

On appelle évenement tout changement dans l’état d’un systeme.

L’ordre sur les évènements est important, par exemple pour

mettre en place une exclusion mutuelle.

Deux évènements ne peuvent avoir lieu exactement en même

temps. Il est toujours possible pour un observateur externe

suffisamment précis de dire quel évenement précede l’autre.

Dans un systeme distribué, les processus n’ont pas acces à

temps global (uniquement des horloges locales plus ou moins

synchronisées). Il est donc très difficile pour un processus de

définir un ordre précis sur les évènements.

Plus grave : deux observations faites par deux processus

différents peuvent différer (dates et ordres des évènements

perçus) ⇒ ”problèmes de décisions cohérentes”

Systèmes Distribués (FSB 2009)

K. Barbaria

4/27

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

Évenements dans un systeme distribué

Peu importe que l’ordre des évènements soit changé (par

rapport à l’ordre défini par un observateur externe) par le

système, il faut surtout qu’il soit le même pour tous les

processus.

Imaginons un compte en banque répliqué sur trois sites selon

le schéma suivant. Quel est le solde final pour chacun des

sites?

ti: opérations de mises à jour (t1=+20;t2=-10;t3=+10%)

Mi : messages pour demander les mises à jour des copies la

Valeur initiale du solde sur chaque site : 200 TND.

Systèmes Distribués (FSB 2009)

K. Barbaria

5/27

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

Causalité

Causalité (Wikipedia)

”En physique, le principe de causalité affirme que si un phénomène

(nommé cause) produit un autre phénomène (nommé effet), alors

l’effet ne peut précéder la cause. À ce jour, il n’a pas été mis en

défaut par l’expérience”

Dans la grande majorité des cas, il n’est pas nécessaire d’avoir

une forte synchronisation des horloges. Il faut surtout mettre

en évidence la dépendance causale entre les évènements.

Il ne jamais contredire le principe de causalité, au risque

d’incohérences graves au niveau du SD.

L’envoi d’un message au niveau d’un site précède forcément

sa réception au niveau d’un autre site.

Systèmes Distribués (FSB 2009)

K. Barbaria

6/27

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

Ordre causal

Relation de précédente causale

Trois lois basiques définissent une relation d’ordre (précède) sur les

évenements d’un systeme distribué. Cette relation est notée “→”.

1 Ordre local: a→b si a et b sont générés dans cet ordre au

niveau d’un même site.

2 Propriété de causalité élémentaire: a→b si a et b sont

respectivement les évènements d’envoi et de réception d’un

même message.

3 Transitivité: si a→b et b→c alors a→c

L’ordre local est facilement établi en utilisant une horloge ou

un compteur (a incrémenter a l’occurrence des évènements)

La relation de précédence causale est une relation d’ordre

partiel : il est possible d’avoir deux évenements impossibles a

classer par cette relation d’ordre : évènements concurrents.

Systèmes Distribués (FSB 2009)

K. Barbaria

7/27

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

Ordre causal (2)

Classer causalement les différents évènements ayant lieu sur

les sites S1, S2 et S3.

Quels sont les évènements 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

Systèmes Distribués (FSB 2009)

K. Barbaria

8/27

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

Ordre causal (3)

Si deux évenements se précedent causalement alors ils se

précèdent réellement (ordre établi par un observateur réel,

externe au système). L’inverse n’est pas vrai. Deux

évenements qui se précedent réellement peuvent ne pas êtres

classés par la relation d’ordre causal (évènements

concurrents).

Concurrence logique : pas de causalité

Concurrence physique : occurrence en même temps physique.

Deux évènements peuvent être concurrents logiquement

même s’ils ne sont pas concurrents physiquement.

Si deux évènements sont en concurrence logique, l’ordre de

leurs exécutions (avant, après, en même temps) ne change pas

le résultat des interactions entre les processus.

Systèmes Distribués (FSB 2009)

K. Barbaria

9/27

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

Ordonnancement des évènements distribués

La relation de précédente causale est fondamentale. Si tous

les processus peuvent avoir le même ordre sur les évènements

qui les intéressent ils pourront interagir sans conflits.

Pour établir un ordre sur les évènements, on leurs associe des

dates en utilisant des horloges.

Propriétés des horloges :

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

corrections, il faut les appliquer en incrémentant l’horloge.

Deux évènements différents ne doivent pas avoir la même date.

Cohérence : Si a → b alors H(a) < H(b)

Systèmes Distribués (FSB 2009)

K. Barbaria

10/27

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

Horloges logiques

La relation de précédence causale permet aux processus de

distinguer les évenements concurrents des évenements qu’ils

doivent traités dans l’ordre.

Il faut donner le moyen aux processus de décider de cette

dépendance causale. Idéalement, il faut donner à chaque

processus le moyne d’établir un ordre total sur tous les

évenements du systeme.

Il est possible pour un processus d’établir un tel ordre en se

basant uniquement sur des informations consultables

localement. Les horloges logiques permettent d’avoir cet

ordre.

Systèmes Distribués (FSB 2009)

K. Barbaria

11/27

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

Algorithme de l’horloge logique (de Lamport)

Objectif : Réaliser une datation des évènements compatible

avec la causalité et définissant un ordre total sur les

évènements.

Algorithme : chaque site Si maintient une variable Hi .

Initialisation : Hi ← 0 ∀i

2 A chaque évènement local sur Si : Hi ← Hi +1;

3 Émission d’un message : évènement local, cause une

incrémentation de Hi . Le message est estampillé par la date de

son émission. ∀m message : H(m) ← H(émission(m))

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

Systèmes Distribués (FSB 2009)

K. Barbaria

12/27

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

Exemple d’application

e11 e12

e13

e14

e15

e21

e22

e23

e24

e25

e31

e32

e33

e34

Systèmes Distribués (FSB 2009)

K. Barbaria

13/27

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

Ordre défini par les horloges logiques

Soient deux évènements a et b, H(a) et H(b) désignent leurs

dates respectives. L’ordre défini par les horloges de Lamport

est noté “<<”. a<<b (a précède 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éfini est total : il est possible d’ordonner tous

les évenements 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é et réplication.

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

pas de dire si un évènement a eu lieu avant l’autre

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

Systèmes Distribués (FSB 2009)

K. Barbaria

14/27

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

Horloges vectorielles

Objectif : On suppose que les sites sont classés de 1 à n.

Algorithme : Chaque site Si maintient un vecteur Vi de

taille n.

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

A chaque évènement local sur Si : Vi [i] ← Vi [i]+1

Émission d’un message : Vi [i] ← Vi [i]+1. Le message est

estampillé par la date de son émission. ∀m message :

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

Réception d’un message m : Vi [i] ← Vi [i]+1 et

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

Systèmes Distribués (FSB 2009)

K. Barbaria

15/27

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

Exemple d’application

000

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èmes Distribués (FSB 2009)

K. Barbaria

16/27

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

Ordre défini 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ésentent exactement la

dépendance causale : ∀a, b evts

a → b ⇔ Va < Vb

a||b ⇔ Va||Vb

Les horloges vectorielles ne définissent pas un ordre total.

Les horloges vectorielles comptent le nombre d’évènements

qui précedent un évenement donné sur l’ensemble des sites. Si

Ve[i ] = m, il y a m évenements qui précedent e sur le site Si

Systèmes Distribués (FSB 2009)

K. Barbaria

17/27

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

Applications et limites

Applications :

Déterminent tous les évènements concurrents

Multicast causalement ordonné.

Vérification de la cohérence de points de reprise.

Limites :

Les vecteurs doivent être transportés avec tous les messages.

Probleme de passage a l’échelle si le nombre de processus est

grand.

Les horloges ne sont pas bornées.

Systèmes Distribués (FSB 2009)

K. Barbaria

18/27

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

Etat global d’un SD : exemple introductif

c21

Un jeton circule entre S1, S2 et S3 (message en pointillé). 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ème

(messages en rouge). Qu’aura t-il en réponse?. Est t-il

possible d’avoir d’autres réponses?

Systèmes Distribués (FSB 2009)

K. Barbaria

19/27

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

Etat global d’un SD : exemple introductif

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

C’est une vision incorrecte de l’état global du système.

Le problème de construire une vision cohérente de l’état

global d’un système distibué est difficile.

Il est impossible d’avoir une vision simultanée des états des

autres processus et des différents canaux de communications.

Il faut donc construire une vision de l’état global à partir de

visions prises à des instants différents mais qui rend une

information utile et cohérente sur le système. Cette vision ne

doit en aucun cas contredire la réalité.

Systèmes Distribués (FSB 2009)

K. Barbaria

20/27

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

Etat global d’un SD

Chaque processus Si possède un état local eli . cet état résulte

de son état initial et de la séquence des évènements ayant lieu

sur le site.

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

pour état ecij l’ensemble des messages en transit (émis par Si

et pas encore reçus par Sj )

Actions influant sur l’état global :

Evenement interne a un site Si : changement de eli

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

Réception d’un message m envoyé de Sj vers Si : cij ← cij − m

L’état global du système est donné par [

eli + [

i ,j

ecij

Systèmes Distribués (FSB 2009)

K. Barbaria

21/27

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

Etat global cohérent

Un état global cohérent est un global compatible avec le

principe de causalité.

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

réception est captée dans elj , soit il appartient à cij

Si l’emission de m n’est pas captée dans eli alors sa réception

n’est pas captée dans elj

Un état global cohérent corrspond à une coupure cohérente

Systèmes Distribués (FSB 2009)

K. Barbaria

22/27

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

Etat global et coupure

Coupure

Une coupure est un ensemble d’évènements contenant au moins un

évèenemement par site.

Coupure cohérente

Une coupure est dite cohérente si elle est fermée par la relation de

dépendance causale. Soit C une couptre , a et b deux evts. C est

cohérente ssi : (a ∈ C et a → b) ⇒ b ∈ C

(a) pas cohérente

(b) cohérente

Systèmes Distribués (FSB 2009)

K. Barbaria

23/27

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

Date d’une coupure

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

V(C) = sup(V (c1), ..., V (cn)), V (ci ) étant l’horloge vectorielle

associée à ci .

100 200

300

010

220

230

240

001

222

243

100 200

300

010

220

230

240

001

232

233

(d) cohérente

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èmes Distribués (FSB 2009)

K. Barbaria

24/27

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

Condition de cohérence d’une coupure

Une coupure C = (c1, ..., cn) est cohérente 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érente!

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

n’est pas cohérente. Le vecteur nous indique d’où vient le

probleme : un évenement sur le site 2.

Systèmes Distribués (FSB 2009)

K. Barbaria

25/27

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

Algorithme de Chandy-Lamport

Envoi d’un marqueur par Si :

1 Si enregistre son état

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

canal avant d’envoyer tout autre message.

Réception d’un marqueur par Sj (par le canal cxj ):

1 Si Sj n’a pas encore enregistré son état, il effectue un envoi de

marqueur comme décrit ci dessus.

2 Sinon Sj met à jour l’état du canal : ecxj ={messages reçus

par ce canal après l’enregistrement de l’état de Sj et avant la

réception du marqueur}

Systèmes Distribués (FSB 2009)

K. Barbaria

26/27

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

Exemple d’application

ec21

ec12

ec23

ec13

Le jeton est capté dans l’état du canal ec12

Reste une phase de construction de l’état global. Les

informations échangent à leurs états locaux (dont la cohérence

est assurée) ainsi que les états des canaux qu’ils ont eregistrés.

Systèmes Distribués (FSB 2009)

K. Barbaria

27/27