Le mod`ele standard

Systèmes distribués
Modélisation
(Tiré depuis le cours de Philippe Queinnec, Gerard Padiou)

A. Messabih

USTO, MI
Département d’informatique

2020/2021

Modèles pour systèmes distribués M2 RSID

 Le modèle standard Approche évènementielle
Causalité
Abstraction d’un calcul

Plan
Modèle standard

• Approche évènementielle
• Causalité
• Abstraction d’un calcul

Modèles pour systèmes distribués M2 RSID

 Le modèle standard Approche évènementielle
Causalité
Abstraction d’un calcul

Modéliser un calcul distribué

Objectifs
Description statique et description comportementale
Abstraction pour faciliter l’analyse
Validation des propriétés (validité et vivacité)

Les éléments de modélisation

Les activités, processus, sites, etc 1⇒ sitelogique
La communication : liens, liaisons, canaux, protocoles (point `a
point, diffusion)...
Les connaissances globales de chaque site logique

Modèles pour systèmes distribués M2 RSID

 Le modèle standard Approche évènementielle
Causalité
Abstraction d’un calcul

Vision statique : Graphe de processus

Graphe structurel (statique)

Sommets ≡ processus / sites
Arcs ≡ liaisons de communication / canaux
P2
c1
c7
P1

c3 c2
P5
c5
c6
c4 P4
P3

Modèles pour systèmes distribués M2 RSID

 Le modèle standard Approche évènementielle
Causalité
Abstraction d’un calcul

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 Défaillance :
pause, arrêt d´efinitif, comportement byzantin

Propriétés du réseau
Multiples paramètres : point à point ou diffusion,
(a)synchrone, fiable, délais bornés, etc
Messages : perte, duplication, modification du contenu

Modèles pour systèmes distribués M2 RSID

 Le modèle standard Approche évènementielle
Causalité
Abstraction d’un calcul

Connaissances d’un processus

Processus

Environnement

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

Modèles pour systèmes distribués M2 RSID

 Le modèle standard Approche évènementielle
Causalité
Abstraction d’un calcul

Système asynchrone

Modèle asynchrone
Pas de temps externe commun
Progression de chaque processus à son rythme
Délai de transmission arbitraire

P1

P2

P3

Modèle réaliste, faibles hypothèses, plus complexe pour développer

et raisonner

Modèles pour systèmes distribués M2 RSID

 Le mod`ele standard Approche évènementielle
Causalité
Abstraction d’un calcul

Système synchrone

Modèle synchrone
Borne connue de délai de communication et de pas de calcul
Pas de calcul (round ) globaux
Un message émis dans un pas est reçu au pas suivant / dans
le même pas (selon le modèle)
Cas particulier : rendez-vous = échange synchrone

r=1 r=2 r =3
P1

P2

P3

Modèle peu réaliste, puissant.

Modèle mixte : sûreté si asynchrone, sûreté + vivacité si synchrone.
Modèles pour systèmes distribués M2 RSID
 Le modèle standard Approche évènementielle
Causalité
Abstraction d’un calcul

Vision dynamique : Chronogramme

Représentation évènementielle
Description globale, dans un repère temporel global
Trois types d’évènements : émission, réception, interne
Modélisation de la communication : diffusion, perte, délais, etc
Causalité entre évènementsi1
e1 e2 r3 e4
A

r'3 e5
B
r2 r1 r4 e6
r"3
C
e3 r5
i2

Modèles pour systèmes distribués M2 RSID

 Le modèle standard Approche évènementielle
Causalité
Abstraction d’un calcul

Relation de causalité (Lamport 1978)

Ordre partiel strict entre évènements ≺

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

La relation ≺ est un ordre partiel: e ǁ ej = e !≺ ej ∧ ej !≺ e

Indépendant du temps physique mais consistent avec :
e ≺ ej ⇒ e est survenu avant ej dans le temps absolu
1. Time, Clocks and the Ordering of Events in a Distributed System, Leslie
Lamport. Communications of the ACM, July 1978.

Modèles pour systèmes distribués M2 RSID

 Le mod`ele standard Approche évènementielle
Causalité
Abstraction d’un calcul

Relation de causalité

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 ǁ c2

Modèles pour systèmes distribués M2 RSID

 Le modèle standard Approche évènementielle
Causalité
Abstraction d’un calcul

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; . . . ƒ≡ c1; a1; a2; . . . car a1 ≺ c1
Le choix des évènements fixe un niveau d’observation

Modèles pour systèmes distribués M2 RSID

 Le modèle standard Approche évènementielle
Causalité
Abstraction d’un calcul

Passé / futur causal

Partition des évènements

Passé(e= {f | f ≺ e}
futur(e) = {f | e ≺ f }
concurrence(e) = {f |f !∈ passé(e) ∧ f !∈ futur(e)}

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

C c1 c4
c2 c3

passé(b2) = {a1, a2, a3, b1} futur(b2) = {a5, b3, b4, c4}
Modèles pour systèmes distribués M2 RSID
 Le modèle standard Approche évènementielle
Causalité
Abstraction d’un calcul

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 : ∀ej : ej ≺ e ⇒ ej ∈ C

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

C c1 c3 c4
c2

Modèles pour systèmes distribués M2 RSID

 Le modèle standard Approche évènementielle
Causalité
Abstraction d’un calcul

Passé et coupure cohérente

Une coupure C est cohérente ssi C = Ue∈C (passe(e) ∪ {e})

Pas de trou sur un site S
Une réception n’est pas présente sans son émission

Exempl
e a 1 a2 a3 KO
a4 OK a
5
A
m2 m4
m1 b1 b3 b4
B b2
m3 m5

C c1 c3 c4
c2

Modèles pour systèmes distribués M2 RSID

 Le modèle standard Approche évènementielle
Causalité
Abstraction d’un calcul

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
Etat effectif
L’état n’a pas existé à un
instant global B
e' r
t'

Modèles pour systèmes distribués M2 RSID

 Le modèle standard Approche évènementielle
Causalité
Abstraction d’un calcul

Treillis des coupures (cohérentes)

Treillis des coupures

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

Treillis des coupures cohérentes

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

Modèles pour systèmes distribués M2 RSID

 Le modèle standard Approche évènementielle
Causalité
Abstraction d’un calcul

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 [Link])

Modèles pour systèmes distribués M2 RSID

 Le modèle standard Approche évènementielle
Causalité
Abstraction d’un calcul

Treillis des coupures cohérentes

Autre exemple

(dessin : cours [Link])

Modèles pour systèmes distribués M2 RSID