Le modèle standard

Description des algorithmes

Systèmes et algorithmes répartis

Modèle standard et principes algorithmiques

Philippe Quéinnec, Gérard Padiou

Département Informatique et Mathématiques Appliquées

ENSEEIHT

26 septembre 2017

Systèmes et algorithmes répartis – II 1 / 43

 Le modèle standard
Description des algorithmes

plan

1 Le modèle standard
Approche événementielle
Causalité
Abstraction d’un calcul
Prise de cliché

2 Description des algorithmes

Description du comportement des processus
Exemple : l’élection

Systèmes et algorithmes répartis – II 2 / 43

 Approche événementielle
Le modèle standard Causalité
Description des algorithmes Abstraction d’un calcul
Prise de cliché

Plan

1 Le modèle standard
Approche événementielle
Causalité
Abstraction d’un calcul
Prise de cliché

2 Description des algorithmes

Description du comportement des processus
Exemple : l’élection

Systèmes et algorithmes répartis – II 3 / 43

 Approche événementielle
Le modèle standard Causalité
Description des algorithmes Abstraction d’un calcul
Prise de cliché

Vision statique : Graphe de processus

Description graphique
Sommets ≡ processus / sites
Arcs ≡ liaisons de communication / canaux

P2
c1
c7
P1

c3 c2
P5
c5
c6
c4 P4
P3

Systèmes et algorithmes répartis – II 4 / 43

 Approche événementielle
Le modèle standard Causalité
Description des algorithmes Abstraction d’un calcul
Prise de cliché

Propriétés
Propriétés des processus / sites
Un processus possède une identité unique
Un processus possède un état rémanent
Un processus exécute un code séquentiellement
Un processus n’a qu’une connaissance partielle des autres
Un processus peut communiquer avec un voisinage
Pas de panne (par arrêt ou comportement byzantin)

Propriétés du réseau
Multiples paramètres : point à point ou diffusion,
(a)synchrone, fiable, délais bornés, etc
Messages : ni duplication ni erreur
Systèmes et algorithmes répartis – II 5 / 43
 Approche événementielle
Le modèle standard Causalité
Description des algorithmes Abstraction d’un calcul
Prise de cliché

Connaissances d’un processus

Processus

Environnement

Nombre de processus ?
Voisinage de communication ?
Structure du réseau : maillé, anneau, statique/dynamique, etc

Systèmes et algorithmes répartis – II 6 / 43

 Approche événementielle
Le modèle standard Causalité
Description des algorithmes Abstraction d’un calcul
Prise de cliché

Vision dynamique : Chronogramme

Représentation événementielle
3 types d’événements : émission, réception, interne
Mise en évidence de la causalité

e1 r2 e3 e4
P1
i1
P2

P3
r1 e2
P4
e5
0 temps

Systèmes et algorithmes répartis – II 7 / 43

 Approche événementielle
Le modèle standard Causalité
Description des algorithmes Abstraction d’un calcul
Prise de cliché

Système asynchrone vs synchrone

Synchrone
Asynchrone
Existence de pas de
Pas de temps externe
calcul (round) globaux
Progression de chaque
Un message émis dans
processus à son rythme
un pas est reçu au pas
Délai de transmission suivant / dans le même
arbitraire pas (selon le modèle)
r=1 r=2 r=3
P1 P1

P2 P2

P3 P3

Systèmes et algorithmes répartis – II 8 / 43

 Approche événementielle
Le modèle standard Causalité
Description des algorithmes Abstraction d’un calcul
Prise de cliché

Relation de causalité (Lamport 1978)

Ordre partiel entre événements ≺

Les événements d’un processus sont totalement ordonnés :
e et e 0 sur le même site, et e précède e 0 , alors e ≺ e 0 .
L’émission d’un message précède causalement sa réception :
Si e = émission(m) et e 0 = réception(m), alors e ≺ e 0 .
Transitivité : ∀e, e 0 , e 00 : e ≺ e 0 ≺ e 00 ⇒ e ≺ e 00

∆
La relation ≺ est un ordre partiel : e k e 0 = e 6≺ e 0 ∧ e 0 6≺ e
Indépendance du temps physique mais consistent avec :
e ≺ e 0 ⇒ e est survenu avant e 0 dans le temps absolu

1. Time, Clocks and the Ordering of Events in a Distributed System, Leslie

Lamport. Communications of the ACM, July 1978.
Systèmes et algorithmes répartis – II 9 / 43
 Approche événementielle
Le modèle standard Causalité
Description des algorithmes Abstraction d’un calcul
Prise de cliché

Relation de causalité (Lamport 1978)

Exemple
a1 a2 a3 a4 a5
A
m2 m4
m1 b1 b3 b4
B
b2 m5
m3
C
c1 c2 c3 c4

a1 ≺ a2 ≺ a3 ≺ a4 ≺ . . .
a1 ≺ c1 , c2 ≺ a4 , b4 ≺ c4
a1 ≺ c3 (car a1 ≺ c1 ≺ c2 ≺ c3 )
a2 ≺ c4
a3 k c2

Systèmes et algorithmes répartis – II 10 / 43

 Approche événementielle
Le modèle standard Causalité
Description des algorithmes Abstraction d’un calcul
Prise de cliché

Abstraction d’un calcul réparti

Exécutions causalement équivalentes

a1 a2 a3 a4 a5
A
m2 m4
m1 b1 b3 b4
B
b2 m5
m3
C
c1 c2 c3 c4

Ensemble d’événements + relation causale

→ ensemble d’exécutions réelles équivalentes
a1 ; b1 ; c1 ; a2 ; . . . ≡ a1 ; a2 ; c1 ; b1 ; . . .
a1 ; c1 ; a2 ; . . . 6≡ c1 ; a1 ; a2 ; . . . car a1 ≺ c1
Le choix des événements fixe un niveau d’observation
Systèmes et algorithmes répartis – II 11 / 43
 Approche événementielle
Le modèle standard Causalité
Description des algorithmes Abstraction d’un calcul
Prise de cliché

Passé / futur causal

Partition des événements
∆
passé(e) = {f | f ≺ e}
∆
futur(e) = {f | e ≺ f }
∆
concurrence(e) = {f |f 6∈ passé(e) ∧ f 6∈ futur(e)}

Exemple
passé(b2) futur(b2)
a1 a2 a3 a4 a5
A
m2 m4
m1 b1 b3 b4
B b2
m3 m5

C c1 c4
c2 c3

Systèmes et algorithmes répartis – II 12 / 43

 Approche événementielle
Le modèle standard Causalité
Description des algorithmes Abstraction d’un calcul
Prise de cliché

Coupure et coupure cohérente

Coupure
Une coupure est un ensemble d’événements qui forment des
préfixes complets des histoires locales.

Coupure cohérente
Une coupure C est cohérente si ∀e ∈ C : ∀e 0 : e 0 ≺ e ⇒ e 0 ∈ C

Exemple
a1 a2 a3 KO OK
a4 a5
A
m2 m4
m1 b1 b3 b4
B b2
m3 m5

C c1 c4
c2 c3

Systèmes et algorithmes répartis – II 13 / 43

 Approche événementielle
Le modèle standard Causalité
Description des algorithmes Abstraction d’un calcul
Prise de cliché

Passé et coupure cohérente

S
Une coupure C est cohérente ssi C = e∈C (passe(e) ∪ {e}) :
Pas de  trou  sur un site
Une réception n’est pas présente sans son émission

Exemple
a1 a2 a3 KO OK
a4 a5
A
m2 m4
m1 b1 b3 b4
B b2
m3 m5

C c1 c4
c2 c3

Systèmes et algorithmes répartis – II 14 / 43

 Approche événementielle
Le modèle standard Causalité
Description des algorithmes Abstraction d’un calcul
Prise de cliché

Coupure cohérente et état global

Une coupure cohérente correspond à un état global qui aurait pu

exister.
E(t)
e r'
A
Réalité
La coupure est
B
e' r cohérente mais. . .
t C
E(t')
e r'
A
État effectif
L’état n’a pas existé à
B
un instant global e' r
t'

Systèmes et algorithmes répartis – II 15 / 43

 Approche événementielle
Le modèle standard Causalité
Description des algorithmes Abstraction d’un calcul
Prise de cliché

Treillis des coupures (cohérentes)

Treillis des coupures

L’ensemble des coupures forme un treillis pour l’inclusion : si C1 et
C2 sont deux coupures, alors C1 ∪ C2 et C1 ∩ C2 sont des coupures

Treillis des coupures cohérentes

L’ensemble des coupures cohérentes forme un treillis pour
l’inclusion : si C1 et C2 sont deux coupures cohérentes, alors
C1 ∪ C2 et C1 ∩ C2 sont des coupures cohérentes

Systèmes et algorithmes répartis – II 16 / 43

 Approche événementielle
Le modèle standard Causalité
Description des algorithmes Abstraction d’un calcul
Prise de cliché

Treillis des coupures cohérentes

Arc du treillis = occurrence

d’un événement possible
Une exécution = suite
d’états globaux cohérents =
chemin dans le treillis
Explosion du nombre d’exécutions causalement équivalentes
(dessins : cours S. Krakowiak)

Systèmes et algorithmes répartis – II 17 / 43

 Approche événementielle
Le modèle standard Causalité
Description des algorithmes Abstraction d’un calcul
Prise de cliché

Treillis des coupures cohérentes

Autre exemple

(dessin : cours S. Krakowiak)

Systèmes et algorithmes répartis – II 18 / 43

 Approche événementielle
Le modèle standard Causalité
Description des algorithmes Abstraction d’un calcul
Prise de cliché

Prise de cliché (snapshot)

Définition
Objectif : Capter, centraliser un état global passé des processus

e1 {}

e2 Prise instantanée impossible

{m4}
{m3}
Un site collecteur accumule
{} Prise cohérente de clichés locaux
e4
e3 Problème des messages en transit
{m1,m2}

Cliché global instantané

Clichés locaux + Messages en transit
{e1 , e2 , e3 , e4 } + {m1 , m2 , m3 , m4 }

Systèmes et algorithmes répartis – II 19 / 43

 Approche événementielle
Le modèle standard Causalité
Description des algorithmes Abstraction d’un calcul
Prise de cliché

Prise de cliché (snapshot)

Schéma temporel de la prise de cliché

e1
{} P1
m0
e1
m4
e2 e2
{m4} P2
m3
{m3} m5
{} P3 e3
e4 m1 m2
e3 P4
{m1,m2} e4

Systèmes et algorithmes répartis – II 20 / 43

 Approche événementielle
Le modèle standard Causalité
Description des algorithmes Abstraction d’un calcul
Prise de cliché

Algorithme de Chandy-Lamport (1985)

Un système existant échange des messages ;

On superpose des échanges de messages dédiés pour
déclencher des actions locales de sauvegarde de l’état d’un
site (= un cliché local + des messages reçus) ;
Ces états sauvegardés sont collectés pour construire un cliché
global.

1. Distributed Snapshots : Determining Global States of Distributed Systems,

K. Mani Chandy and Leslie Lamport. ACM Transactions on Computer Systems,
Feb. 1985
Systèmes et algorithmes répartis – II 21 / 43
 Approche événementielle
Le modèle standard Causalité
Description des algorithmes Abstraction d’un calcul
Prise de cliché

Algorithme de Chandy-Lamport (1985)

Idée
Matérialiser la coupe par la circulation d’un marqueur visitant
les sites
Les messages émis après le passage du marqueur ne peuvent
pas être dans la coupe
Les messages émis par Sj avant le passage du marqueur sur
Sj , et reçus par Si après le passage du marqueur sur Si , sont
considérés comme les messages en transit de Sj vers Si

Hypothèse
Canaux FIFO (pas de perte, pas de dépassement)

Systèmes et algorithmes répartis – II 22 / 43

 Approche événementielle
Le modèle standard Causalité
Description des algorithmes Abstraction d’un calcul
Prise de cliché

Algorithme de Chandy-Lamport (1985)

Hypothèses
Réseau fortement connexe (∀s, s 0 : ∃s →∗ s 0 )
Canaux unidirectionnels et fifo :
∀s, Rc(s) : canaux en réception
Em(s) : canaux en émission
S

Principes de l’algorithme
Utilisation de messages marqueurs
Rc(s) Em(s)
Répartition de l’évaluation : chaque site s
évalue :
son cliché local ;
les messages considérés en transit sur ses
canaux en réception Rc(s)

Systèmes et algorithmes répartis – II 23 / 43

 Approche événementielle
Le modèle standard Causalité
Description des algorithmes Abstraction d’un calcul
Prise de cliché

Algorithme de Chandy-Lamport

Comportement d’un site

Sur réception d’un PREMIER marqueur ou spontanément :
1 Prendre son cliché local Ls et émettre un marqueur sur
chaque canal d’émission c ∈ Em(s)
2 Enregistrer dans une liste enTransit[c] les messages reçus sur
chaque canal de réception c ∈ Rc(s) jusqu’à la réception d’un
marqueur sur ce canal
3 Lorsqu’un marqueur a été reçu sur TOUS les canaux de
réception, communiquer au collecteur cet état partiel :
hLs , {enTransit[c] | c ∈ Rc(s)}i

Systèmes et algorithmes répartis – II 24 / 43

 Approche événementielle
Le modèle standard Causalité
Description des algorithmes Abstraction d’un calcul
Prise de cliché

Prises de clichés locaux et marqueurs

Prise de cliché Réception du marqueur

Réception des messages en transit issu de B

issus de B

e r’
A Message
marqueur
m m’
Message
en transit
B
e’ r

Première arrivée du marqueur => prise de cliché local

Systèmes et algorithmes répartis – II 25 / 43

 Approche événementielle
Le modèle standard Causalité
Description des algorithmes Abstraction d’un calcul
Prise de cliché

Vérifier la correction. . .
Propriétés
Sûreté
Coupure cohérente
Collecte complète des messages en transit
Vivacité
Tout site finit par prendre un cliché local
Un marqueur finit par arriver sur chaque canal de réception

Exemple
Cohérence de la coupure Séquence en transit complète
e e
A A
impossible
marqueur impossible
marqueur
B r B
r
C C

Systèmes et algorithmes répartis – II 26 / 43

 Approche événementielle
Le modèle standard Causalité
Description des algorithmes Abstraction d’un calcul
Prise de cliché

État enregistré = état possible

État enregistré
Σenreg = cliché enregistré
Σinit = coupure cohérente contenant l’événement déclencheur
du cliché
Σfinal = coupure cohérente dans lequel le protocole de prise
de cliché est terminé
Alors Σinit ≺ Σenreg ≺ Σfinal

(il existe un chemin de Σinit à Σfinal passant par Σenreg dans le

treillis des coupures cohérentes)

Exemple : sur le treillis page 17, si Σinit = Σ11 et Σfinal = Σ32 ,

Σenreg peut être Σ11 , Σ21 , Σ12 , Σ31 , Σ22 ou Σ32 , et a pu ne pas
être traversé dans la réalité.
Systèmes et algorithmes répartis – II 27 / 43
 Approche événementielle
Le modèle standard Causalité
Description des algorithmes Abstraction d’un calcul
Prise de cliché

Utilisation du cliché : propriété stable

Prédicat stable
Un prédicat P sur un état global E d’un système est stable ssi
∀E 0 : E ≺ E 0 ∧ P(E ) ⇒ P(E 0 )

(exemples : le calcul est terminé, il y a eu 10 messages reçus. . . )

Vérification de P
Si P est un prédicat stable alors :
P(Σenreg ) ⇒ P(Σfinal ) (et tout état ultérieur)
¬P(Σenreg ) ⇒ ¬P(Σinit ) (et tout état antérieur)

Systèmes et algorithmes répartis – II 28 / 43

 Approche événementielle
Le modèle standard Causalité
Description des algorithmes Abstraction d’un calcul
Prise de cliché

Utilisation du cliché : propriété possible/certaine

Prédicat possible/certain
Pour un prédicat P :
Pos(P) (possibly P) : il existe une observation cohérente (=
un chemin dans le treillis) qui passe par un état où P est vrai.
Def (P) (definitely P) : toutes les observations cohérentes (=
tous les chemins) passent par un état où P est vrai.

Vérification
P(Σenreg ) ⇒ Pos(P) mais pas l’inverse. . .
¬Pos(P) ⇒ Def (¬P) mais pas l’inverse. . .

Systèmes et algorithmes répartis – II 29 / 43

 Approche événementielle
Le modèle standard Causalité
Description des algorithmes Abstraction d’un calcul
Prise de cliché

Exemple de vérification de propriétés

x=3 x=4 x=5

e1 0 e1 1
e1 2 e1 3
e1 5
e1 6
e1 4

e2 0 e2 1 e2 2 e2 3 e2 4 e2 5
y=6 y=4 y=2

x ≥ 4 ? (en supposant x croissant ⇒ propriété stable)

Pos(x = y − 2) ?
Def (x = y ) ?

(d’après Lorenzo Alvisi)

Systèmes et algorithmes répartis – II 30 / 43

 Approche événementielle
Le modèle standard Causalité
Description des algorithmes Abstraction d’un calcul
Prise de cliché

Exemple de vérification
Propriété stable

00

10 01

11 02

21 12 03
x ≥ 4?
31 22 13
(sous l’hypothèse x
41 32 23
croissant)
42 33
N’importe quel cliché Σenreg
43
obtenu après Σ31 permet de
53 44
le vérifier
63 54 45
64 55
65

Systèmes et algorithmes répartis – II 31 / 43

 Approche événementielle
Le modèle standard Causalité
Description des algorithmes Abstraction d’un calcul
Prise de cliché

Exemple de vérification
Possibilité

00

10 01

11 02

21 12 03 Pos(x = y − 2) ?
31 22 13 x = y − 2 est vrai dans les
41 32 23 états cohérents Σ31 et Σ41
42 33 Détecté uniquement si
43
Σenreg ∈ {Σ31 , Σ41 }
53 44 Σenreg pas nécessairement
63 54 45
survenu dans la réalité
64 55
65

Systèmes et algorithmes répartis – II 32 / 43

 Approche événementielle
Le modèle standard Causalité
Description des algorithmes Abstraction d’un calcul
Prise de cliché

Exemple de vérification
Certitude
00

10 01

11 02
Def (x = y ) ?
21 12 03
Vrai
31 22 13
Pos(x = y ) pas détecté si
41 32 23
on capture un état antérieur
42 33
à Σ32 ou postérieur à Σ54
43 La capture d’un état (p.e.
53 44 Σ42 ) ne permet pas de
63 54 45 conclure
64 55
65
Systèmes et algorithmes répartis – II 33 / 43
 Approche événementielle
Le modèle standard Causalité
Description des algorithmes Abstraction d’un calcul
Prise de cliché

Utilisation du cliché : propriété possible/certaine

Principe de la vérification

Un processus moniteur M collecte tous les états locaux

M construit le treillis des coupures cohérentes (à partir d’un
codage complet de la relation de causalité, cf chapitre suivant)
Pour évaluer Pos(P) : parcourir le treillis depuis l’état initial,
niveau par niveau, et s’arrêter au premier état où P est vrai.
Aucun état ⇒ ¬Pos(P).
Pour évaluer Def (P) : parcourir le treillis depuis l’état initial,
niveau par niveau, en ne développant que les états vérifiant
¬P. Si plus d’état, alors Def (P) ; si état final atteint (et ¬P
dans cet état) alors ¬Def (P).
Explosion combinatoire : pour N sites ayant chacun au plus m
états, possiblement mN coupures cohérentes.
Systèmes et algorithmes répartis – II 34 / 43
 Le modèle standard Description du comportement des processus
Description des algorithmes Exemple : l’élection

Plan

1 Le modèle standard
Approche événementielle
Causalité
Abstraction d’un calcul
Prise de cliché

2 Description des algorithmes

Description du comportement des processus
Exemple : l’élection

Systèmes et algorithmes répartis – II 35 / 43

 Le modèle standard Description du comportement des processus
Description des algorithmes Exemple : l’élection

Principes algorithmiques

Algorithmes symétriques
code répliqué,
données initiales propres : identité, voisinage de
communication.
Structurer les échanges de messages :
Utilisation de réseaux en anneau
Utilisation de la structure d’arbre
Étudier des problèmes génériques :
Les services : datation, exclusion mutuelle, consensus,
élection. . .
Les observations de propriétés stables : terminaison,
interblocage
La tolérance aux fautes : réplication, atomicité

Systèmes et algorithmes répartis – II 36 / 43

 Le modèle standard Description du comportement des processus
Description des algorithmes Exemple : l’élection

Description des algorithmes

Process P(id : 0..N-1)
<variables locales>
on <condition-logique> :
<Action>
on reception message(arg) [ from P(j) ] :
<Action>
on <condition-logique> ∧ reception message(arg) :
<Action>
on start : // initialement
<Action>
...
Action : modification des variables locales et/ou envoi(s) de
message, ou terminaison (terminate)
Envoi : send Msg(<args>) to <destinataire(s)>
Choix d’un événement à traiter : non déterministe parmi ceux
ayant la garde vraie et un message à consommer
Systèmes et algorithmes répartis – II 37 / 43
 Le modèle standard Description du comportement des processus
Description des algorithmes Exemple : l’élection

Exemple : l’élection
Le problème de l’élection
Objectif : Élire un seul processus
mozart
bach berlioz

verdi
vivaldi
grieg

Un processus a une identité unique qu’il connaı̂t

Un processus ne connaı̂t pas le nombre global de processus
Un processus ne connaı̂t pas l’identité des autres
Communication sur un anneau logique
1. An improved algorithm for decentralized extrema-finding in circular
configurations of processes, Ernest Chang and Rosemary Roberts.
Communications of the ACM, May 1979.
Systèmes et algorithmes répartis – II 38 / 43
 Le modèle standard Description du comportement des processus
Description des algorithmes Exemple : l’élection

Solution correcte ou fausse ?

On suppose que les processus sont totalement ordonnés (ici par
leur indice, en pratique, par leur adresse IP par exemple)

Process P(id : 0..N-1)

// et ⊕ : opérateurs modulo N
type Etat = {candidat,élu};
Etat étatCourant ← candidat;
on reception Candidat(proc) from P[id 1] :
if (proc < id) send Candidat(proc) to P[id⊕1];
else if (proc = id) étatCourant ← élu;
else nop; // ignorer le message
on (étatCourant = élu) :
terminate;

Pourquoi cela ne marche-t-il pas ?

Systèmes et algorithmes répartis – II 39 / 43
 Le modèle standard Description du comportement des processus
Description des algorithmes Exemple : l’élection

Solution qui conduit à l’élection du plus petit

Process P(id : 0..N-1)

type Etat = {candidat,élu};
Etat étatCourant ← candidat;
on start:
send Candidat(id) to P[id⊕1]; // chacun candidate
on reception Candidat(proc) from P[id 1]:
if (proc < id) send Candidat(proc) to P[id⊕1];
else if (proc = id) étatCourant ← élu;
else nop; // ignorer le message
on (étatCourant = élu) :
terminate;

Pas parfait : un seul processus se termine

Systèmes et algorithmes répartis – II 40 / 43
Solution plus complète : tous les processus terminent
Process P(id :0..N-1) {
type Etat = {candidat,élu,perdant};
Etat étatCourant ← candidat;
on start :
send Candidat(id) to P[id⊕1]; // chacun candidate
on reception Candidat(proc) from P[id 1]:
if (proc < id) send Candidat(proc) to P[id⊕1];
else if (proc = id) étatCourant ← élu;
else nop; // ignorer le message
on (étatCourant = élu) :
send Elu(id) to P[id⊕1];
on reception Elu(proc) from P[id 1]:
if (proc 6= id) then
étatCourant ← perdant;
send Elu(proc) to P[id⊕1];
endif
terminate
 Le modèle standard Description du comportement des processus
Description des algorithmes Exemple : l’élection

Déclenchement spontané individuel

Pas nécessairement tous candidats au départ (mais tous éligibles)

Process P(id : 0..N-1)

type Etat = {candidat,élu,perdant};
Etat étatCourant ← candidat;
on random() :
send Candidat(id) to P[id⊕1];
on reception Candidat(proc) from P[id 1]:
if (proc < id) send Candidat(proc) to P[id⊕1];
else if (proc = id) étatCourant ← élu;
else if (proc > id) send Candidat(id) to P[id⊕1];
.
.
.

Systèmes et algorithmes répartis – II 42 / 43

 Le modèle standard Description du comportement des processus
Description des algorithmes Exemple : l’élection

Conclusion

Modélisation par des événements locaux

Relation entre ces événements, en particulier la causalité
Représentation avec des chronogrammes
Notion d’état global, de coupure
Calcul d’un état global

Systèmes et algorithmes répartis – II 43 / 43