Modèle standard et principes algorithmiques

Le modele standardDescription des algorithmes

Systemes et algorithmes repartisModele standard et principes algorithmiques

Philippe Queinnec, Gerard Padiou

Departement Informatique et Mathematiques AppliqueesENSEEIHT

26 septembre 2017

Systemes et algorithmes repartis – II 1 / 43


plan

1 Le modele standardApproche evenementielleCausaliteAbstraction d’un calculPrise de cliche

2 Description des algorithmesDescription du comportement des processusExemple : l’election



Approche evenementielleCausaliteAbstraction d’un calculPrise de cliche

Plan






Vision statique : Graphe de processus

Description graphique

Sommets ≡ processus / sites

Arcs ≡ liaisons de communication / canaux

P1

P2

P3 P4

c1

c2

c4

c5

c3P5

c7

c6




Proprietes

Proprietes des processus / sites

Un processus possede une identite unique

Un processus possede un etat remanent

Un processus execute un code sequentiellement

Un processus n’a qu’une connaissance partielle des autres

Un processus peut communiquer avec un voisinage

Pas de panne (par arret ou comportement byzantin)

Proprietes du reseau

Multiples parametres : point a point ou diffusion,(a)synchrone, fiable, delais bornes, etc

Messages : ni duplication ni erreur




Connaissances d’un processus

Environnement

Processus

Nombre de processus ?

Voisinage de communication ?

Structure du reseau : maille, anneau, statique/dynamique, etc




Vision dynamique : Chronogramme

Representation evenementielle

3 types d’evenements : emission, reception, interne

Mise en evidence de la causalite

e1 r2 e3 e4

i1

e2r1

e5

temps

P1

P2

P3

P4

0




Systeme asynchrone vs synchrone

Asynchrone

Pas de temps externe

Progression de chaqueprocessus a son rythme

Delai de transmissionarbitraire

Synchrone

Existence de pas decalcul (round) globaux

Un message emis dansun pas est recu au passuivant / dans le memepas (selon le modele)

P1

P2

P3

r = 1 r = 2 r = 3P1

P2

P3




Relation de causalite (Lamport 1978)

Ordre partiel entre evenements ≺Les evenements d’un processus sont totalement ordonnes :e et e ′ sur le meme site, et e precede e ′, alors e ≺ e ′.

L’emission d’un message precede causalement sa reception :Si e = emission(m) et e ′ = reception(m), alors e ≺ e ′.

Transitivite : ∀e, e ′, e ′′ : e ≺ e ′ ≺ e ′′ ⇒ e ≺ e ′′

La relation ≺ est un ordre partiel : e ‖ e ′ ∆= e 6≺ e ′ ∧ e ′ 6≺ e

Independance du temps physique mais consistent avec :e ≺ e ′ ⇒ e est survenu avant e ′ dans le temps absolu

1. Time, Clocks and the Ordering of Events in a Distributed System, LeslieLamport. Communications of the ACM, July 1978.




Relation de causalite (Lamport 1978)

Exemplea1 a2 a3 a4 a5

b1

b2

b3 b4

A

B

Cc2 c3c1

m3

m4

c4

m5

m2m1

a1 ≺ a2 ≺ a3 ≺ a4 ≺ . . .a1 ≺ c1, c2 ≺ a4, b4 ≺ c4

a1 ≺ c3 (car a1 ≺ c1 ≺ c2 ≺ c3)a2 ≺ c4

a3 ‖ c2




Abstraction d’un calcul reparti

Executions causalement equivalentesa1 a2 a3 a4 a5

b1

b2

b3 b4

A

B

Cc2 c3c1

m3

m4

c4

m5

m2m1

Ensemble d’evenements + relation causale→ ensemble d’executions reelles equivalentes

a1; b1; c1; a2; . . . ≡ a1; a2; c1; b1; . . .a1; c1; a2; . . . 6≡ c1; a1; a2; . . . car a1 ≺ c1

Le choix des evenements fixe un niveau d’observation




Passe / futur causal

Partition des evenements

passe(e)∆= {f | f ≺ e}

futur(e)∆= {f | e ≺ f }

concurrence(e)∆= {f |f 6∈ passe(e) ∧ f 6∈ futur(e)}

Exemple

a1 a2 a3 a4 a5

b1

b2

b3 b4

A

B

Cc2 c3c1

m3

m4

c4

m5

m2m1

passé(b2) futur(b2)




Coupure et coupure coherente

Coupure

Une coupure est un ensemble d’evenements qui forment desprefixes complets des histoires locales.

Coupure coherente

Une coupure C est coherente si ∀e ∈ C : ∀e ′ : e ′ ≺ e ⇒ e ′ ∈ C

Exemple

a1 a2 a3 a4 a5

b1

b2

b3 b4

A

B

Cc2 c3c1

m3

m4

c4

m5

m2m1

OKKO




Passe et coupure coherente

Une coupure C est coherente ssi C =⋃

e∈C (passe(e) ∪ {e}) :

Pas de � trou � sur un site

Une reception n’est pas presente sans son emission

Exemple

a1 a2 a3 a4 a5

b1

b2

b3 b4

A

B

Cc2 c3c1

m3

m4

c4

m5

m2m1

OKKO




Coupure coherente et etat global

Une coupure coherente correspond a un etat global qui aurait puexister.

A

B

e

re'

r'

Ct

E(t)

Realite

La coupure estcoherente mais. . .

Etat effectif

L’etat n’a pas existe aun instant global

A

B

e

re'

r'

t'

E(t')




Treillis des coupures (coherentes)

Treillis des coupures

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

Treillis des coupures coherentes

L’ensemble des coupures coherentes forme un treillis pourl’inclusion : si C1 et C2 sont deux coupures coherentes, alorsC1 ∪ C2 et C1 ∩ C2 sont des coupures coherentes




Treillis des coupures coherentes

Arc du treillis = occurrenced’un evenement possible

Une execution = suited’etats globaux coherents =chemin dans le treillis

Explosion du nombre d’executions causalement equivalentes

(dessins : cours S. Krakowiak)




Treillis des coupures coherentesAutre exemple

(dessin : cours S. Krakowiak)




Prise de cliche (snapshot)

Definition

Objectif : Capter, centraliser un etat global passe des processus

e1

e2

e3e4

{}{m3}

{m4}

{}

{m1,m2}

Prise instantanee impossible

Un site collecteur accumule

Prise coherente de cliches locaux

Probleme des messages en transit

Cliche global instantane

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




Prise de cliche (snapshot)Schema temporel de la prise de cliche

e1

e2

e3e4

{}{m3}

{m4}

{}

{m1,m2}

P1P2P3P4

m3

m2m1

m0 m4

e1e2

e3e4

m5




Algorithme de Chandy-Lamport (1985)

Un systeme existant echange des messages ;

On superpose des echanges de messages dedies pourdeclencher des actions locales de sauvegarde de l’etat d’unsite (= un cliche local + des messages recus) ;

Ces etats sauvegardes sont collectes pour construire un clicheglobal.

1. Distributed Snapshots : Determining Global States of Distributed Systems,K. Mani Chandy and Leslie Lamport. ACM Transactions on Computer Systems,Feb. 1985





Idee

Materialiser la coupe par la circulation d’un marqueur visitantles sites

Les messages emis apres le passage du marqueur ne peuventpas etre dans la coupe

Les messages emis par Sj avant le passage du marqueur surSj , et recus par Si apres le passage du marqueur sur Si , sontconsideres comme les messages en transit de Sj vers Si

Hypothese

Canaux FIFO (pas de perte, pas de depassement)





Hypotheses

Reseau fortement connexe (∀s, s ′ : ∃s →∗ s ′)Canaux unidirectionnels et fifo :∀s, Rc(s) : canaux en reception

Em(s) : canaux en emission

Principes de l’algorithme

Utilisation de messages marqueurs

Repartition de l’evaluation : chaque site sevalue :

son cliche local ;les messages consideres en transit sur sescanaux en reception Rc(s)

Rc(s)

S

Em(s)




Algorithme de Chandy-Lamport

Comportement d’un site

Sur reception d’un PREMIER marqueur ou spontanement :

1 Prendre son cliche local Ls et emettre un marqueur surchaque canal d’emission c ∈ Em(s)

2 Enregistrer dans une liste enTransit[c] les messages recus surchaque canal de reception c ∈ Rc(s) jusqu’a la reception d’unmarqueur sur ce canal

3 Lorsqu’un marqueur a ete recu sur TOUS les canaux dereception, communiquer au collecteur cet etat partiel :

〈Ls , {enTransit[c] | c ∈ Rc(s)}〉




Prises de cliches locaux et marqueurs

r

e r’

e’B

A

m m’

Messagemarqueur

Prise de clichéissu de BRéception des messages en transit

issus de B

Messageen transit

Réception du marqueur

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




Verifier la correction. . .

Proprietes

Surete

Coupure coherenteCollecte complete des messages en transit

Vivacite

Tout site finit par prendre un cliche localUn marqueur finit par arriver sur chaque canal de reception

Exemple

A

BC

r

e A

B

e

rC

impossible

Séquence en transit complète

marqueur

impossible

Cohérence de la coupure

marqueur




Etat enregistre = etat possible

Etat enregistre

Σenreg = cliche enregistre

Σinit = coupure coherente contenant l’evenement declencheurdu cliche

Σfinal = coupure coherente dans lequel le protocole de prisede cliche est termine

Alors Σinit ≺ Σenreg ≺ Σfinal

(il existe un chemin de Σinit a Σfinal passant par Σenreg dans letreillis des coupures coherentes)

Exemple : sur le treillis page 17, si Σinit = Σ11 et Σfinal = Σ32,Σenreg peut etre Σ11, Σ21, Σ12, Σ31, Σ22 ou Σ32, et a pu ne pasetre traverse dans la realite.




Utilisation du cliche : propriete stable

Predicat stable

Un predicat P sur un etat global E d’un systeme est stable ssi∀E ′ : E ≺ E ′ ∧ P(E )⇒ P(E ′)

(exemples : le calcul est termine, il y a eu 10 messages recus. . . )

Verification de P

Si P est un predicat stable alors :

P(Σenreg )⇒ P(Σfinal ) (et tout etat ulterieur)

¬P(Σenreg )⇒ ¬P(Σinit) (et tout etat anterieur)




Utilisation du cliche : propriete possible/certaine

Predicat possible/certain

Pour un predicat P :

Pos(P) (possibly P) : il existe une observation coherente (=un chemin dans le treillis) qui passe par un etat ou P est vrai.

Def (P) (definitely P) : toutes les observations coherentes (=tous les chemins) passent par un etat ou P est vrai.

Verification

P(Σenreg )⇒ Pos(P) mais pas l’inverse. . .

¬Pos(P)⇒ Def (¬P) mais pas l’inverse. . .




Exemple de verification de proprietes

e10 e1

1 e12 e1

3e1

4 e15 e1

6

e20 e2

1 e22 e2

3 e24 e2

5

x = 3 x = 4 x = 5

y = 6 y = 4 y = 2

x ≥ 4 ? (en supposant x croissant ⇒ propriete stable)

Pos(x = y − 2) ?

Def (x = y) ?

(d’apres Lorenzo Alvisi)




Exemple de verificationPropriete stable

10 01

00

11 02

12 03

13

21

22

23

31

32

33

41

42

43

44

45

53

54

55

63

64

65

x ≥ 4 ?(sous l’hypothese xcroissant)

N’importe quel cliche Σenreg

obtenu apres Σ31 permet dele verifier




Exemple de verificationPossibilite

10 01

00

11 02

12 03

13

21

22

23

31

32

33

41

42

43

44

45

53

54

55

63

64

65

Pos(x = y − 2) ?

x = y − 2 est vrai dans lesetats coherents Σ31 et Σ41

Detecte uniquement siΣenreg ∈ {Σ31,Σ41}Σenreg pas necessairementsurvenu dans la realite




Exemple de verificationCertitude

10 01

00

11 02

12 03

13

21

22

23

31

32

33

41

42

43

44

45

53

54

55

63

64

65

Def (x = y) ?

Vrai

Pos(x = y) pas detecte sion capture un etat anterieura Σ32 ou posterieur a Σ54

La capture d’un etat (p.e.Σ42) ne permet pas deconclure




Utilisation du cliche : propriete possible/certainePrincipe de la verification

Un processus moniteur M collecte tous les etats locaux

M construit le treillis des coupures coherentes (a partir d’uncodage complet de la relation de causalite, cf chapitre suivant)

Pour evaluer Pos(P) : parcourir le treillis depuis l’etat initial,niveau par niveau, et s’arreter au premier etat ou P est vrai.Aucun etat ⇒ ¬Pos(P).

Pour evaluer Def (P) : parcourir le treillis depuis l’etat initial,niveau par niveau, en ne developpant que les etats verifiant¬P. Si plus d’etat, alors Def (P) ; si etat final atteint (et ¬Pdans cet etat) alors ¬Def (P).

Explosion combinatoire : pour N sites ayant chacun au plus metats, possiblement mN coupures coherentes.



Description du comportement des processusExemple : l’election

Plan






Principes algorithmiques

Algorithmes symetriques

code replique,donnees initiales propres : identite, voisinage decommunication.

Structurer les echanges de messages :

Utilisation de reseaux en anneauUtilisation de la structure d’arbre

Etudier des problemes generiques :

Les services : datation, exclusion mutuelle, consensus,election. . .Les observations de proprietes stables : terminaison,interblocageLa tolerance aux fautes : replication, atomicite




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) demessage, ou terminaison (terminate)Envoi : send Msg(<args>) to <destinataire(s)>

Choix d’un evenement a traiter : non deterministe parmi ceuxayant la garde vraie et un message a consommer




Exemple : l’election

Le probleme de l’election

Objectif : Elire un seul processus

bachmozart

grieg

berlioz

vivaldiverdi

Un processus a une identite unique qu’il connaıt

Un processus ne connaıt pas le nombre global de processus

Un processus ne connaıt pas l’identite des autres

Communication sur un anneau logique

1. An improved algorithm for decentralized extrema-finding in circularconfigurations of processes, Ernest Chang and Rosemary Roberts.Communications of the ACM, May 1979.




Solution correcte ou fausse ?

On suppose que les processus sont totalement ordonnes (ici parleur indice, en pratique, par leur adresse IP par exemple)


// et ⊕ : operateurs modulo Ntype Etat = {candidat,elu};Etat etatCourant ← candidat;

on reception Candidat(proc) from P[id1] :

if (proc < id) send Candidat(proc) to P[id⊕1];else if (proc = id) etatCourant ← elu;

else nop; // ignorer le message

on (etatCourant = elu) :

terminate;

Pourquoi cela ne marche-t-il pas ?Systemes et algorithmes repartis – II 39 / 43



Solution qui conduit a l’election du plus petit


type Etat = {candidat,elu};Etat etatCourant ← candidat;

on start:

send Candidat(id) to P[id⊕1]; // chacun candidate

on reception Candidat(proc) from P[id1]:if (proc < id) send Candidat(proc) to P[id⊕1];else if (proc = id) etatCourant ← elu;



terminate;

Pas parfait : un seul processus se termine


Solution plus complete : tous les processus terminent

Process P(id :0..N-1) {type Etat = {candidat,elu,perdant};Etat etatCourant ← candidat;

on start :

send Candidat(id) to P[id⊕1]; // chacun candidate

on reception Candidat(proc) from P[id1]:if (proc < id) send Candidat(proc) to P[id⊕1];else if (proc = id) etatCourant ← elu;



send Elu(id) to P[id⊕1];on reception Elu(proc) from P[id1]:

if (proc 6= id) then

etatCourant ← perdant;

send Elu(proc) to P[id⊕1];endif

terminate



Declenchement spontane individuel

Pas necessairement tous candidats au depart (mais tous eligibles)


type Etat = {candidat,elu,perdant};Etat etatCourant ← candidat;

on random() :

send Candidat(id) to P[id⊕1];on reception Candidat(proc) from P[id1]:

if (proc < id) send Candidat(proc) to P[id⊕1];else if (proc = id) etatCourant ← elu;

else if (proc > id) send Candidat(id) to P[id⊕1];...




Conclusion

Modelisation par des evenements locaux

Relation entre ces evenements, en particulier la causalite

Representation avec des chronogrammes

Notion d’etat global, de coupure

Calcul d’un etat global


Documents

Modèle standard et principes algorithmiques