Cours 3 - Causalité Et Datation

Problème de datation
Les protocoles de communication
Systèmes et algorithmes répartis

Causalité et datation
Philippe Quéinnec, Gérard Padiou
Département Informatique et Mathématiques Appliquées

ENSEEIHT
3 octobre 2017
Systèmes et algorithmes répartis – III 1 / 29

Problème de datation
Les protocoles de communication
plan
1 Problème de datation
Temps réel vs temps logique
Horloge de Lamport
Horloge vectorielle de Fidge-Mattern
2 Les protocoles de communication

Délivrance ordonnée
Protocoles ordonnés
Protocole causalement ordonné
Diffusion causalement ordonnée

Problème de datation Horloge de Lamport
Les protocoles de communication Horloge vectorielle de Fidge-Mattern
Plan
Horloge de Lamport


Problème de base et difficultés

Comment dater les événements d’une exécution répartie ?
Pas d’horloge globale
Tous les événements ne sont pas causalement liés
Datation cohérente avec la relation causale :
∀e, e 0 : e ≺ e 0 ⇒ de < de 0
Exemple
Idée : → Utiliser les horloges matérielles de chaque site
Risque : Datation incohérente de l’événement de réception
d’un message : la date de réception précède la date d’émission
Possible si l’horloge du site de réception est en retard
(suffisamment) sur celle du site de l’émetteur

Temps réel
Difficultés
Cohérence avec la causalité
Datation définissant un ordre total
Solutions
Nécessite une synchronisation des horloges locales :
invariant max (hi ) − min (hi ) <

i=1..N i=1..N
Protocole de synchronisation d’horloges possible mais dans des

contextes réseaux assurant une certaine qualité de service ou par
l’usage d’un signal diffusé (horloge atomique)

Temps logique
Principes de base
Compter les événements au lieu du temps réel
Associer à chaque site une horloge logique locale
Surcharger les messages avec leur date d’émission
Recaler si nécessaire l’horloge locale d’un site lors de chaque
réception de message
Avantage : vision plus abstraite d’un calcul réparti

Une tentative. . .
Un compteur horloge sur chaque site
Surcharge des messages et recalage de compteur
(1) (2) (3) (6)
0 a1 1 a2 2 a3 3 a4 6
A
<1,m1> <3,m2> <5,m3> (6)
0 4 5 b3 6
B
b1 b2
<6,m4>
(4) (5)
0 2 3 7
C
c1 c2 c3
Recalage
(2) (3) (7)
, e ≺ e 0 ⇒ d(e) < d(e 0 )

, Mêmes dates ⇒ pas causalement liés
/ mais d(e) < d(e 0 ) ; e ≺ e 0 (ex : d(c2 ) < d(b3 ) ; c2 ≺ b3 )
Horloge de Lamport
Propriétés
Introduit un ordre total entre événements
→ Dates distinctes pour tout couple d’événements
Date = (numéro de site, compteur local)
⇒ ordre total sur les sites (par leur numéro)
struct Date { int s; // numéro de site

int cpt; // compteur d’événements
}
bool prec (Date d1, Date d2) {
return (d1.cpt < d2.cpt)
|| ((d1.cpt == d2.cpt) && (d1.s < d2.s));
}
1. Time, Clocks and the Ordering of Events in a Distributed System, Leslie
Lamport. Communications of the ACM, July 1978.
Actions associées aux événements
L’événement est daté avec le résultat de l’action.

Type d’événement sur un site s Action sur le site s
Événement interne sur s Hs ← Hs + 1;
Émission sur s de m Hs ← Hs + 1;
envoi de hHs , mi ;
Réception sur s de hdm, mi Hs ← max(Hs , dm) + 1;
(A,1) (A,2) (A,3) (A,6) (A,7)
0 a1 1 a2 2 a3 3 a4 6 a5 7
A
<(A,3),m2> <(B,5),m3>
<(A,1), m1> <(A,7),m5>
B 0 4 5 6
b1 b2 b3
(B,4) <(B,6),m4>
(B,5) (B,6)
0 2 3 7 8
C
c1 c2 c3 c4 c5
(C,2) (C,3) (C,7) (C,8) (C,9)

Horloge vectorielle de Fidge-Mattern (1988)

Propriétés
datation isomorphe à l’ordre causal
utilisation de vecteurs de dimension égale au nombre de sites
coût plus élevé : surcharge des messages par un vecteur
Pour un événement e, HV (e)[i] = nombre d’événements du
passé de e sur pi (y compris e)
Expression des relations entre dates
∆
D ≤ D 0 = ∀i : D[i] ≤ D 0 [i]
∆
D < D 0 = D ≤ D 0 ∧ ∃k : D[k] < D 0 [k]
∆
D k D 0 = ¬(D < D 0 ) ∧ ¬(D 0 < D)
1. Timestamps in Message-Passing Systems That Preserve the Partial
Ordering, Colin J. Fidge. 11th Australian Computer Science Conference, 1988.
2. Virtual Time and Global State in Distributed Systems, Friedemann
Mattern. Int’l Workshop on Parallel and Distributed Algorithms, 1989.
L’événement est daté avec le résultat de l’action.

Événement interne sur s Hs [s] ← Hs [s] + 1
Émission sur s de m Hs [s] ← Hs [s] + 1
envoi de hHS , mi
Réception sur s de hdm, mi Hs [s] ← Hs [s] + 1
Hs [s 0 ] ← max(Hs [s 0 ], dm[s 0 ]), ∀s 0 6= s
(0,0,0) a1 (1,0,0) a2 (2,0,0) a3 (3,0,0) a4 (4,2,0)
A
<(3,0,0),m2> <(3,2,0),m3>
<(1,0,0), m1>
(0,0,0) (3,1,0) (3,2,0) (3,3,0)
B
b1 b2 b3 <(3,3,0),m4>
C (0,0,0) (1,0,1) (1,0,2) (3,3,3)

c1 c2 c3


Datation isomorphe à l’ordre causal
e ≺ e 0 ⇔ D(e) ≤ D(e 0 ) et e k e 0 ⇔ D(e) k D(e 0 )
Coupure
Date d’une coupure C = (c1 , . . . , cn ) :
∆
HV (C ) = sup(HV (c1 ), . . . , HV (cn ))
C2 ⊂ C1 ⇔ HV (C2 ) < HV (C1 )
C cohérente ⇔ HV (C ) = hHV (c1 )[1], . . . , HV (cn )[n]i
Soit C cohérente. Alors ∀i, j : HV (ci )[i] ≥ HV (cj )[i].

En effet, l’incrémentation de HV (ci )[i] ne peut venir que d’un événement
local ou résulter d’un message provenant du passé.
Soit C non cohérente.
⇒ il existe un événement ei hors coupe qui est dans le passé causal de C
⇒ Sur le site i : HV (ci )[i] < HV (ei )[i] et HV (ei )[i] ≤ HV (C )[i]
⇒ HV (C )[i] > HV (ci )[i], donc HV (C ) 6= (HV (c1 )[1], . . . , HV (cn )[n])
Problème de datation Protocoles ordonnés
Les protocoles de communication Protocole causalement ordonné
Plan
Horloge de Lamport


Protocole FIFO
e1 e2 e1 e2
S1 m2
m1 m1 m2
S2 r2 r1 r1 r2
Non FIFO FIFO
m m0
∀m, m0 : s1 −→ s2 ∧ s1 −→ s2 ∧ e(m) ≺ e(m0 ) ⇒ r (m) ≺ r (m0 )
e1 e2
S1 m2
m1
S2 r2 r1 d1 d2
délivrance 6= réception

Objectif : Mettre de l’ordre

Réceptions incohérentes par rapport aux émissions
e1 e2
P1
m2
e3
P2 m3
r2 m1
P3
r3 r1
r3 ≺ r1 alors que e1 ≺ e3
⇒ délivrance 6= réception
1. Reliable communication in the presence of failures, Kenneth P. Birman and

Thomas A. Joseph. ACM Transactions on Computer Systems, January 1987.
Protocole FIFO
Objectif
Garantir la cohérence des réceptions sur un même site par rapport
à leur éventuelle émission depuis un même site
⇒ réordonner les messages reçus sur un site
Trois événements au lieu de deux par message :

l’émission e,
la réception r ,
la délivrance d.
Causalité : e ≺ r ≺ d
S’exprime par la propriété :
m m0
∀s1 , s2 , m, m0 : s1 −→ s2 ∧ s1 −→ s2 ∧ e(m) ≺ e(m0 )
⇒ d(m) ≺ d(m0 )

Protocole FIFO
Réalisation : il suffit de numéroter les messages pour chaque canal
(couple site d’émission, site de réception)
Récepteur pour un canal :
type Message = hcontenu, numéroi;
int prochain = 0;
SortedSet<Message> enAttente; // trié par numéro
while (true) {
recevoir m;
enAttente.add(m);
while (enAttente.first().numéro == prochain) {
m ← enAttente.removeFirst();
délivrer m.contenu
prochain++;
}
}
Objectif
Garantir la cohérence des réceptions sur un même site par rapport
à leur causalité éventuelle en émission
⇒ réordonner les messages reçus sur un site
Trois événements au lieu de deux par message :

l’émission e,
la réception r ,
la délivrance d.
Causalité : e ≺ r ≺ d
S’exprime par la propriété :
m m0
∀s, m, m0 : −→ s ∧ −→ s ∧ e(m) ≺ e(m0 )
⇒ d(m) ≺ d(m0 )

Histoire causale
Histoire causale d’un message Hc (m)

L’histoire causale Hc (m) d’un message m est l’ensemble des
messages qui ont leurs événements d’émission précédant
causalement l’émission de m :
Hc (m) = {m0 : e(m0 ) ≺ e(m)}
Critère de délivrance d’un message

Un message m est délivré sur un site s ssi tous les messages de son
histoire causale ayant aussi s comme site de destination ont été
déjà délivrés :
m m0
∀s, m0 ∈ Hc (m) : −→ s ∧ −→ s ∧ ⇒ d(m0 ) ≺ d(m)

Histoire causale : exemple
Exemple
Hc (m10 ) = {m8 , m4 , m9 , m7 , m1 , m6 , m3 , m2 }
Hc (m6 ) = {m3 }
Hc (m8 ) = {m4 , m1 , m2 }
Approche par surcharge (piggybacking)

Principe
Surcharger chaque message avec l’histoire des messages qui le
précèdent causalement
Dans le contexte du courrier électronique : Approche similaire
du réexpédier avec copie de ce que l’on a reçu
Exemple
e1 e
A
<m1,C>,m
<>,m1
e2
B
r
<(m1,C);(m,B)>, m2
C
r2 d1 d2 r1
message ignoré

Approche par surcharge (piggybacking)
Mise en œuvre
, Simple et apport d’une certaine tolérance aux pertes de
messages par redondance
/ Messages de + en + longs
⇒ Quand, Comment réduire les histoires ?
Exemple
A
<(m1,C)>,m3
<>,m1 <(m1,C);...>,m5
B
<(m1,C)>,m2 <(m2,B);(m3,B)>,m4
Éliminer (m1,C)
car B sait que C a reçu m1

Datation, premier essai. . .
Datation causale (horloge vectorielle)

Permet la détection des anomalies en réception MAIS pas leur
prévention
e1 e
A
1
< 0 ,M1>
0 e2
B
r 2
< 2 ,M2>
0
C
r2 r1
2 1
2 0
0 0

Approche par compteurs

Structures de données
Représenter l’histoire causale de chaque message
Chaque site Ss gère :
MPs : une matrice de précédence causale
MPs [i, j] = nombre de messages émis de Si vers Sj ,
connu de Ss
Derniers : un vecteur de compteurs des messages reçus de
chaque site
Derniers [i] = nombre de messages reçus du site Si sur Ss
Tout message est surchargée par une copie de la matrice MP
du site émetteur
1. The Causal Ordering Abstraction and a Simple Way to Implement it,
Michel Raynal, André Schiper and Sam Toueg. Information Processing Letters,
1991.

Émission sur s de m vers s 0 MPs [s, s 0 ] + +
envoi de hMPs , Mi
Réception sur s de hMP, mi MPs ← max(MP, MPs )
issu de s 0 Derniers [s 0 ] + +
∆
Délivrance sur s de hMP, mi Délivrable(m) =
issu de s 0 Derniers [s 0 ] = MP[s 0 , s]
∧ ∀i 6= s : Derniers [i] ≥ MP[i, s]
∆
m délivrable = FIFO entre s 0 et s et il ne précède pas les
messages dont l’émission le précède causalement.

Contrôle des délivrances

Horloges de plus en plus précises

Horloges de Lamport
Passé de l’ensemble du système, connu de s, réduit à la longueur
de la plus longue chaı̂ne causale aboutissant à l’événement
Horloges vectorielles
Connaissance de premier ordre : passé de s 0 que s connaı̂t,
connaissance par s que s 0 a eu un certain nombre d’événements
Horloges matricielles
Connaissance de second ordre : connaissance par s de la
connaissance par s 0 du passé de s 00 .
Par exemple, permet de savoir que tous les sites connaissent un

événement donné

La diffusion ordonnée est plus simple que la communication point-à-point !
Approche par matrice causale
Il suffit de gérer un vecteur d’émission au lieu d’une matrice
Toutes les lignes sont identiques : un processus envoie le
même nombre de messages à tous
A (1,0,0)
(1,0,0) (1,1,0)
Défaut de
(1,1,1)
B causalité
(1,1,0) Vecteur local (a,b,c)
C (0,0,0)
1. Lightweight Causal and Atomic Group Multicast, Kenneth P. Birman,

André Schiper and Pat Stephenson. ACM Transactions on Computer Systems,
1991.
Conclusion
Datation logique des événements

Protocoles de communication ordonnés
Distinction réception / délivrance

Cours 3 - Causalité Et Datation

Transféré par

Droits d'auteur :

Formats disponibles

Cours 3 - Causalité Et Datation

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Cours 3 - Causalité Et Datation

Transféré par

Droits d'auteur :

Formats disponibles

Problème de datation

Les protocoles de communication

Systèmes et algorithmes répartis

Philippe Quéinnec, Gérard Padiou

Département Informatique et Mathématiques Appliquées

Systèmes et algorithmes répartis – III 1 / 29

2 Les protocoles de communication

Systèmes et algorithmes répartis – III 2 / 29

2 Les protocoles de communication

Systèmes et algorithmes répartis – III 3 / 29

Problème de base et difficultés

Systèmes et algorithmes répartis – III 4 / 29

invariant max (hi ) − min (hi ) < 

Protocole de synchronisation d’horloges possible mais dans des

Systèmes et algorithmes répartis – III 5 / 29

Systèmes et algorithmes répartis – III 6 / 29

, e ≺ e 0 ⇒ d(e) < d(e 0 )

struct Date { int s; // numéro de site

Actions associées aux événements

L’événement est daté avec le résultat de l’action.

Systèmes et algorithmes répartis – III 9 / 29

Horloge vectorielle de Fidge-Mattern (1988)

Actions associées aux événements

L’événement est daté avec le résultat de l’action.

C (0,0,0) (1,0,1) (1,0,2) (3,3,3)

Systèmes et algorithmes répartis – III 11 / 29

Horloge vectorielle de Fidge-Mattern

Soit C cohérente. Alors ∀i, j : HV (ci )[i] ≥ HV (cj )[i].

2 Les protocoles de communication

Systèmes et algorithmes répartis – III 13 / 29

Systèmes et algorithmes répartis – III 14 / 29

Protocole causalement ordonné

Objectif : Mettre de l’ordre

1. Reliable communication in the presence of failures, Kenneth P. Birman and

Trois événements au lieu de deux par message :

Systèmes et algorithmes répartis – III 16 / 29

Protocole causalement ordonné

Trois événements au lieu de deux par message :

Systèmes et algorithmes répartis – III 18 / 29

Histoire causale d’un message Hc (m)

Hc (m) = {m0 : e(m0 ) ≺ e(m)}

Critère de délivrance d’un message

Systèmes et algorithmes répartis – III 19 / 29

Histoire causale : exemple

Approche par surcharge (piggybacking)

Systèmes et algorithmes répartis – III 21 / 29

Approche par surcharge (piggybacking)

Systèmes et algorithmes répartis – III 22 / 29

Datation, premier essai. . .

Datation causale (horloge vectorielle)

Systèmes et algorithmes répartis – III 23 / 29

Approche par compteurs

Actions associées aux événements

Type d’événement sur un site s Action sur le site s

Systèmes et algorithmes répartis – III 25 / 29

Contrôle des délivrances

Systèmes et algorithmes répartis – III 26 / 29

Horloges de plus en plus précises

Par exemple, permet de savoir que tous les sites connaissent un

invariant max (hi ) − min (hi ) <