5.1.2 Mod le dinterblocage OUET . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

68

5.2 Condition de d blocage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

69

5.3 D nition de linterblocage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

70

5.4 Trois strat gies contre linterblocage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

71

5.5 Pr vention dans le mod le ET avec lalgorithme de Rosenkrantz, Stearns et Lewis, 1978 . . . .

73

5.5.1 Exercice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

74

5.6 D tection dinterblocage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

75

76

5.6.1 Coupure coh rente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.6.2 Algorithme centralis de construction de coupure coh rente de Chandy et Lamport, 1985 77

78

5.6.3 Exercice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6 D tection de terminaison

6.1 Mod le OU de linterblocage

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.2 Congurations terminale et nale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.3 tats actif et passif, et algorithme de contr le . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.4 Algorithmes de d tection de terminaison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.5 D tection par calcul du graphe dex cution . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.5.1 Algorithme de Dijkstra et Scholten, 1980

. . . . . . . . . . . . . . . . . . . . . . . . . .

6.5.2 Exercice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.6 D tection par vagues dans un anneau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.6.1 Algorithme de Safra, 1987 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.6.2 Exercice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Bibliographie

Index

Fin

79

80

81

82

83

84

85

87

88

89

91

92

93

95

T l com SudParis Denis Conan Avril 2020 CSC4509

3

Initiation lalgorithmique r partie

Licence

$

Ce document est une documentation libre, plac e sous la Licence de Documentation Libre GNU (GNU

Free Documentation License).

Copyright (c) 2003-2020 Denis Conan

Permission est accord e de copier, distribuer et/ou modifier ce document selon les

termes de la Licence de Documentation Libre GNU (GNU Free Documentation License),

version 1.2 ou toute version ult rieure publi e par la Free Software Foundation; avec

les Sections Invariables qui sont Licence ; avec les Textes de Premi re de Couverture

qui sont Initiation lalgorithmique r partie

et avec les Textes de Quatri me de Couverture qui sont Fin.

Une copie de la pr sente Licence peut tre trouv e ladresse suivante :

http://www.gnu.org/copyleft/fdl.html.

2

Remarque : La licence comporte notamment les sections suivantes : 2. COPIES VERBATIM, 3. COPIES

EN QUANTIT , 4. MODIFICATIONS, 5. M LANGE DE DOCUMENTS, 6. RECUEILS DE

DOCUMENTS, 7. AGR GATION AVEC DES TRAVAUX IND PENDANTS et 8. TRADUCTION.

&

%

Ce document est pr par avec des logiciels libres :

" LATEX :

les

textes

sources

sont crits en LATEX (http://www.latex-project.org/,

le site

du Groupe francophone des Utilisateurs de TEX/LATEX est http://www.gutenberg.eu.org).

la classe seminar ont

Une nouvelle

t

fusionforge slideint,

tout

https://fusionforge.int-evry.fr/www/slideint/);

sp cialement d v lopp es: newslide et slideint (projet

et une nouvelle

style bas es

feuille de

classe

sur

" emacs: tous les textes sont dit s avec l diteur GNU emacs (http://www.gnu.org/software/emacs);

" dvips: les versions PostScript (PostScript est une marque d pos e de la soci t Adobe Systems In-

corporated) des transparents et des polycopi s destination des tudiants ou des enseignants sont

obtenues partir des chiers DVI ( DeVice Independent ) g n r s partir de LaTeX par lutilitaire

dvips (http://www.ctan.org/tex-archive/dviware/dvips);

" ps2pdf et dvipdfmx: les versions PDF (PDF est une marque d pos e de la soci t Adobe Sys-

tems Incorporated) sont obtenues partir des chiers Postscript par lutilitaire ps2pdf (ps2pdf

tant un shell-script lan ant Ghostscript, voyez le site de GNU Ghostscript http://www.gnu.org/-

software/ghostscript/) ou partir des chiers DVI par lutilitaire dvipfmx;

" makeindex:

les

index et glossaire

sont g n r s laide de

lutilitaire Unix makeindex

(http://www.ctan.org/tex-archive/indexing/makeindex);

" TeX4ht: les pages HTML sont g n r es partir de LaTeX par TeX4ht (http://www.cis.ohio-

-state.edu/~gurari/TeX4ht/mn.html);

" Xfig: les gures sont dessin es dans lutilitaire X11 de Fig xfig (http://www.xfig.org);

" fig2dev: les gures sont export es dans les formats EPS ( Encapsulated PostScript ) et PNG

( Portable Network Graphics ) gr ce lutilitaire fig2dev (http://www.xfig.org/userman/-

installation.html);

" convert: certaines gures sont converties dun format vers un autre par lutilitaire convert

(http://www.imagemagick.org/www/utilities.html) de ImageMagick Studio;

" HTML TIDY:

les sources HTML g n r s par TeX4ht sont beauti s laide de HTML TIDY

(http://tidy.sourceforge.net) ; vous pouvez donc les lire dans le source.

Nous esp rons que vous regardez cette page avec un navigateur libre: Firefox par exemple. Comme lindique

le choix de la licence GNU/FDL, tous les l ments permettant dobtenir ces supports sont libres.

Ce cours a b n ci des relectures attentives et constructives de Fran ois Meunier, L on Lim.

T l com SudParis Denis Conan Avril 2020 CSC4509

4

Initiation lalgorithmique r partie

Utilisation du cours

$

Apprentissage en formation en ligne

f D marche conseill e :

3

Pour chaque page du support de cours, tudiez la page du support de cours

(diapositive + commentaires)

tude des exercices en pr sentiel

Puis auto- valuation des connaissances avec les QCM (une s rie par section)

Les QCM ainsi que les corrig s des exercices sont fournis part dans moodle

&

%

NB : Certaines pages du cours sont marqu es par un ast risque ( * ) la n de leur titre. Ceci

correspond un contenu dapprofondissement. Ne l tudiez pas en d tail avant de ma triser les autres points

de la section. Ces diapositives doivent tre tudi es avant de faire certaines questions (optionnelles) des

exercices.

T l com SudParis Denis Conan Avril 2020 CSC4509

5

Initiation lalgorithmique r partie

Plan du document

$

4

1 l ments introductifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2 lection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3 Diusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

4 Exclusion mutuelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

5 Interblocage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

6 D tection de terminaison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

&

%

Une d nition commun ment admise dun syst me r parti est : plusieurs ordinateurs inter-connect s

par un ensemble de r seaux de communication eectuant un travail ensemble et communicant par change

de messages . Cette d nition sugg re deux propri t s principales des syst mes r partis : la non-unicit de

lieu (un utilisateur travaille en local ou distance) et la non-unicit de temps (chaque ordinateur poss de

sa propre notion du temps travers son horloge physique). Par ailleurs, cette d nition di re de celle

dun syst me parall le (ou dit fortement coupl ) dans lequel les communications peuvent seectuer via une

m moire partag e et dans lequel il y a unicit de lieu et de temps.

Les syst mes r partis sont diciles concevoir et comprendre parce quils ne sont pas intuitifs. Peut-

tre est-ce aussi parce que notre vie est, par bien des aspects, fondamentalement s quentielle ? Nous devons

donc d velopper une intuition pour la r partition. Dans cette discipline, il existe une tension in vitable entre

les partisans de la mod lisation et de lanalyse, et ceux de lobservation exp rimentale. Cette tension illustre

la dichotomie classique entre la th orie et la pratique. Dans ce cours dalgorithmique r partie, nous nous

placerons plus du c t pratique.

Nous commen ons par la pr sentation du mod le de syst me r parti dans la section introductive. Ensuite,

les probl mes tudi s sont des probl mes fondamentaux basiques de lalgorithmique r partie partir desquels

sont construites des architectures de services r partis complexes. Le principe de l lection est de partir dune

conguration dans laquelle tous les processus sont dans le m me tat, pour arriver dans une conguration

dans laquelle un seul processus est dans l tat gagnant et tous les autres dans l tat perdant . La

diusion est une primitive de communication permettant un processus denvoyer le m me message

tous les autres processus en respectant des propri t s dordre (FIFO, causal, total) dans la transmission des

messages. Lexclusion mutuelle consiste faire circuler un jeton entre des processus r partis sur le r seau pour

nautoriser quun seul dentre eux entrer en section critique. Cest lexpression r partie des s maphores.

Linterblocage se produit lorsquun ensemble de processus est tel que chacun deux tient au moins une

ressource, et pour poursuivre sa progression, est en attente dune ressource tenue par lun des autres. Des

algorithmes sont propos s pour pr venir ou d tecter les interblocages. La d tection de terminaison autorise

quun algorithme r parti se termine de fa on implicite, cest- -dire sans que les processus atteignent leur

tat nal (n du processus par appel de la fonction exit), autrement dit, parce quil ny a plus de travail

faire (tous les processus sont en attente dun message et les canaux de communication sont vides).

T l com SudParis Denis Conan Avril 2020 CSC4509

6

Initiation lalgorithmique r partie

$

1 l ments introductifs

5

1.1 Mod le de syst me r parti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.2 Conventions de codage des algorithmes r partis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.3 Relation arriv avant aussi appel e pr c dence causale, Lamport 1978 . . . . . . . 11

1.4 Vague et travers e de graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

&

%

Cette section introductive est reprise des r f rences suivantes :

" G. Tel, Chapter 2 : The Model, dans Introduction to Distributed Algorithms, Cambridge University

Press, pp. 4372, 1994.

" C. Fidge. Logical Time in Distributed Computing Systems, dans IEEE Computer, pages 2833, August

1991.

" G. Tel, Chapter 6 : Wave and traversal algorithms, dans Introduction to Distributed Algorithms, Cam-

bridge University Press, pp. 177221, 1994.

" H. Attiya et J. Welch, Chapter 2 : Basic Algorithms in Message-Passing Systems, dans Distributed

Computing : Fundamentals, simulation, and advanced topics, Wiley, pp. 930, 2004.

" J.H. Saltzer, M.F. Kaashoek, Principles of Computer System Design : An Introduction, Morgan Kauf-

mann, 2009.

Le premier l ment dintroduction est le mod le de syst me r parti. Ce mod le base de messages est

utilis dans tout le reste du cours. Il est assez g n ral pour tre utile aussi bien lors de la conception que lors

de la v rication (m me si nous ne nous focalisons par sur les preuves des algorithmes tudi s). Puis, nous

introduisons les conventions de codage utilis es dans ce cours : soit lorientation contr le soit lorientation

v nement. Ensuite, le dernier l ment g n ral introduit pour la suite du cours est la notion de d pendance

causale qui permet de construire un ordre partiel des v nements dune ex cution r partie. Enn, parmi les

probl mes fondamentaux que nous tudions, beaucoup peuvent sexprimer laide de sous-t ches g n riques

comme les vagues. Cest par exemple le cas de la diusion ou de la d tection dinterblocage tudi e un peu

plus loin dans ce cours. Nous pr sentons donc la n de cette section le principe des algorithmes de vagues

et y ferons r f rence dans les autres sections.

T l com SudParis Denis Conan Avril 2020 CSC4509

7

Initiation lalgorithmique r partie

1 l ments introductifs

$

1.1 Mod le de syst me r parti

6

1.1.1 Mod le de transitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.1.2 Synchronisme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.1.3 Types de d faillances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

&

%

Les param tres du syst me r parti les plus discriminants sont les suivants : synchronisme ( performance

des nSuds et du r seau), type de fautes des nSuds et des communications (cat gorie de fautes mat rielles

et logicielles ), topologie (forme du graphe du syst me de communication) et

d terminismes des processus (comportement pr visible des algorithmes r partis). Ces hypoth ses sont im-

portantes car elles conditionnent les r sultats dimpossibilit (comme latteinte dun consensus) ainsi que les

approches algorithmiques. Par exemple, il nexiste pas de solution d terministe tous les probl mes dans

tous les cas. Mais, avant de d tailler ces l ments discriminants, nous pr sentons les l ments constitutifs du

mod le, cest- -dire dans notre cas ceux du mod le de transitions.

Ce cours se limite l tude des algorithmes r partis d terministes. Ainsi, nous ne pr sentons pas dalgo-

rithme avec comportement al atoire, par exemple ceux du type Las Vegas (avec une solution correcte

mais une distribution probabiliste sur la dur e dex cution) ou ceux du type Monte Carlo (avec une

probabilit sur la correction de la solution mais un bornage de cette probabilit ).

T l com SudParis Denis Conan Avril 2020 CSC4509

8

1 l ments introductifs

1.1 Mod le de syst me r parti

$

1.1.1 Mod le de transitions

7

Algorithme : assigne des valeurs des variables

Processus : ex cution dun algorithme sur un nSud du syst me r parti

Canal de communication : lien logique r seau entre deux processus

Ex cution = tat initial puis succession dactions sur les tats

tat global ou conguration = juxtaposition d tats locaux, un par processus

Histoire = s quence des actions dun processus

f Histoire r partie = ensemble des histoires locales des processus

R partition = actions internes, d mission et de r ception

Toute propri t est ou se d compose en propri t s de :

f Correction (en anglais, safety ) : une assertion est vraie dans chaque

conguration de lalgorithme

f Vivacit ou progression (en anglais, liveness) : une assertion est vraie dans

certaines congurations de chaque ex cution

&

%

Tous les mod les de sp cication pour les syst mes r partis sont bas s sur la notion daction atomique

et de machine tats. Parmi les mod les les plus couramment choisis, citons le mod le des transitions, le

mod le des actions temporelles logiques, et le mod le des automates (pouvant tre temporis s). Dans ce

cours, nous utilisons le mod le le plus simple, celui dit des transitions, que nous d crivons maintenant.

Un algorithme assigne des valeurs des variables. Un tat est laectation de valeurs des variables.

Une action (encore appel e un v nement) a repr sente la relation entre un ancien tat s et un nouvel tat

t not e sat. Les actions sont atomiques : laction a provoque le changement instantan de l tat de s

t. Autrement dit, on nobserve pas l tat du syst me pendant lex cution de a.

Un algorithme s quentiel A est un objet syntaxique construit selon la grammaire dun langage de pro-

grammation. Une ex cution de lalgorithme s quentiel A dans un processus P d butant linstant t partir

de l tat initial s0, est la succession dun nombre inni dactions sur des tats not e a0s0a1s1a2s2a3, etc.

L tat s0 est appel l tat initial. Laction initiale a0 est ctive et correspond la cr ation du processus

P . Lex cution dun algorithme s quentiel produit donc une s quence dactions. La s quence dactions est

appel e lhistoire de lalgorithme s quentiel. De fa on duale, lorsquil sagit de formuler ou de d montrer une

propri t , il est souvent tr s int ressant de mod liser une ex cution comme tant une s quence d tats, une

action tant la transition dun tat un autre 1,2.

Un algorithme r parti A est compos dalgorithmes s quentiels ex cut s dans des processus P1...Pn qui

communiquent par change de messages. Laction d mission mettre(Pj, m) dun message m de Pi vers Pj

ajoute m au canal cij. Pratiquement, m est transmis de Pi vers Pj par le r seau de communication et est

gard dans la m moire du nSud o sex cute Pj. Laction de r ception recevoir(m) dun message m par Pj

sur lensemble des canaux cij assigne m le premier message arriv par lun des canaux. Si aucun message

nest arriv alors Pj attend jusqu larriv e dun message par lun des canaux. Toute action autre quune

action d mission ou de r ception dun message est appel e une action interne.

L tat dun canal cij linstant physique t est constitu de lensemble des messages mis et non encore

re us. L tat global (encore appel conguration) s dun syst me r parti linstant physique t est compos

des tats locaux de tous les processus du syst me r parti linstant t. Lex cution dun algorithme r parti

d butant linstant physique t partir de la conguration s est constitu e de la juxtaposition des ex cutions

des processus. Par d duction, lhistoire r partie dun syst me r parti est constitu e de la juxtaposition des

histoires des processus.

1. R.W. Floyd. Assigning meanings to programs. In J.T. Schwartz, editor, Proceedings of Symposia in Applied Mathema-

tics, Mathematical Aspects of Computer Science, volume 19, pages 1932, Providence, Rhode Island, USA, 1967. American

Mathematical Society.

2. C.A.R. Hoare. An Axiomatic Basis for Computer Programming. Communications of the ACM, 12(10):576580, October

1969.

T l com SudParis Denis Conan Avril 2020 CSC4509

9

1 l ments introductifs

1.1 Mod le de syst me r parti

Le mod le que nous venons de d nir est appel le mod le de transitions sous lhypoth se de communi-

cation asynchrone : les op rations d mission ne sont pas bloquantes alors que les op rations de r ception le

sont. Dans le cas des communications synchrones, les op rations d mission sont elles-aussi bloquantes. Dans

ce cas, clairement, dans toutes les congurations dans lesquelles tous les processus viennent dex cuter une

action interne, les canaux sont vides.

Lex cution dun algorithme r parti est classiquement repr sent e par un diagramme de s quences ( la

UML) aussi appel diagramme temporel ou chronogramme. La gure qui suit trace un tel diagramme pour

un algorithme r parti compos de trois algorithmes s quentiels. Le d roulement du temps est d crit par une

ligne continue (ligne qui est tiret et sappelle ligne de vie en UML) pour chaque algorithme s quentiel.

Les actions sont symbolis es par des tirets sur les lignes de vie . Les messages sont mat rialis s par des

ches connectant une action mettre une action recevoir.

Enn, dans un syst me r parti, il est important de faire la distinction entre les propri t s de s ret

ou correction (en anglais, safety property) et de progression ou vivacit (en anglais, liveness property). La

propri t de s ret dun algorithme est de la forme lassertion est vraie dans chaque conguration de

lalgorithme , ou encore de fa on informelle lassertion est toujours vraie . Pratiquement, la propri t de

s ret sert exprimer que quelque chose de non d sir narrive pas. La technique de base pour montrer que

lassertion est toujours vraie est de d montrer que cest un invariant : vrai dans l tat de d part de lex cution,

et si vrai dans la conguration atteignable s alors vrai dans toutes les congurations atteignables directement

partir de s. La propri t de vivacit dun algorithme quant elle stipule que lassertion est vraie dans

certaines congurations de chaque ex cution de lalgorithme , ou encore que lassertion est vraie terme

ou ultimement . La technique de base pour montrer que lassertion est vraie terme est soit dutiliser une

autre propri t de vivacit (par exemple, le message est re u terme par un processus atteignable car tous

les canaux de communication du syst me transmettent in ne tous les messages mis par l metteur du

canal), soit par induction en utilisant une m trique qui progresse dans le temps jusqu atteindre un seuil

auquel lassertion est vraie (pour le m me exemple, parmi chaque pas dex cution consid rant l mission ou

la r ception dun message, de temps en temps, il y a un message qui sapproche de r cepteur en r cepteur

du destinataire nal, la m trique utilis e tant le nombre de processus entre l metteur initial et le

destinataire nal).

T l com SudParis Denis Conan Avril 2020 CSC4509

10

222233331230123023aaaaaaaaa42a25a4a26a35a3a276a2a38713Temps1716151121101PPP134aaaaaaaa1 l ments introductifs

1.1 Mod le de syst me r parti

$

1.1.2 Synchronisme

8

Synchronea :

' Dur e de transmission dun message dun nSud un autre born e et borne

connue

' Dur e d x cution dune action interne dun processus born e et borne connue

Asynchrone :

( Pas de borne ou borne inconnue sur la transmission dun message

( Pas de borne ou borne inconnue sur la d rive des horloges

( Pas de borne ou borne inconnue sur la dur e dun traitement

a. Il est important de ne pas confondre synchronisme des communications et synchronisme du

syst me. Ici, cest le synchronisme du syst me qui est consid r .

&

%

Un syst me r parti est dit synchrone si et seulement si :

" la dur e de transmission dun message dun nSud un autre est born e et la borne est connue ; et,

" la dur e dex cution dune action interne dun processus est born e et la borne est connue.

Dans un tel syst me r parti, un processus mettant un message peut faire lhypoth se quil est re u, voire

trait , apr s une dur e limite calculable (car les bornes sont connues).

Un syst me r parti est dit asynchrone sil nexiste pas de borne (connue ou non) sur la transmission

dun message, la d rive des horloges ou la dur e dex cution dune action interne. Dans la pratique, construire

un algorithme pour un syst me asynchrone signie ne pas soccuper des caract ristiques mat rielles (qualit

des nSuds ou des communications). En dautres termes, d s que des aspects temporels sont introduits dans

les algorithmes (hypoth se sur les dur es dex cution ou de transmission, test de abilit de transmission

laide de temporisation, etc.), le syst me consid r nest plus compl tement asynchrone , mais dit

partiellement asynchrone . Lacception partiellement asynchrone recouvre le mod le synchrone et

trente-et-un autres mod les, tous entre compl tement asynchrone et synchrone 1. Nous ne d taillons

pas ces nombreux mod les et nabordons pas la tol rance aux fautes dans ce manuscrit. Cest lobjectif des

tudes darticles r alis es par groupe dans le cadre du module.

1. D. Dolev, C. Dwork, and L. Stockmeyer, On the minimal synchronism needed for distributed consensus, Journal of the

ACM, 34(1), January 1987.

T l com SudParis Denis Conan Avril 2020 CSC4509

11

1 l ments introductifs

1.1 Mod le de syst me r parti

$

1.1.3 Types de d faillances

9

Hormis lorsque pr cis , les algorithmes pr sent s ne tol rent pas les d faillances

Dans tous les cas, les d faillances arbitraires sont exclues de l tude

&

%

Un processus ou un nSud (dans le cas o lon ne consid re quun processus par nSud) est dit d faillant

lors dune ex cution si son comportement di re de la sp cication de lalgorithme quil ex cute. Sinon, il

est dit correct . Il en est de m me pour les canaux de communication entre processus. Un mod le

de d faillances d nit les d faillances rencontr es (et prises en compte ou tol r es). La litt rature liste

commun ment les types de d faillances suivants :

" arr t franc initial (en anglais, initial crash) : un processus nex cute aucune action de son algorithme

local, autre que laction initiale. Ce type de d faillance nest pas montr sur la gure ; il se trouverait

avant le nSud arr t franc dans le graphe ;

" arr t franc (en anglais, crash) : un processus sarr te pr matur ment et ne fait rien ensuite ; avant

larr t, son ex cution est correcte. Dans le cas dun canal de communication, celui-ci est d nitivement

coup ;

" omission sur mission : un processus sarr te pr matur ment, omet d mettre des messages par

intermittence ou les deux. Dans le cas dun canal de communication, lomission sur mission correspond

une perte de messages. Par exemple, un processus jetant des messages parce que son cache de messages

en mission est plein, subit des omissions sur mission ;

" omission sur r ception : un processus sarr te pr matur ment, omet de recevoir des messages

par intermittence ou les deux. Dans le cas dun canal de communication, lomission sur r ception

correspond une perte de messages. Par exemple, un processus jetant des messages parce que son

cache de messages en r ception est plein, subit des omissions sur r ception ;

" omission g n rale : un processus est sujet omission sur mission ou sur r ception, voire les deux ;

" arbitraire, byzantine1 ou maligne : un processus peut tre sujet nimporte quel comportement,

y compris de la malveillance (de la part dun utilisateur) ; par opposition, les d faillances pr c dentes

sont dites b nignes . Pour un canal de communication, cela correspond la perte, la duplication,

la corruption (violation de lint grit ), voire la g n ration spontan e dun message.

Ces types de d faillances peuvent tre class s en termes de s v rit . La gure ordonne les types de

d faillances, des d faillances les moins s v res (arr t francs) au plus s v res (arbitraires). Un algorithme

tol rant les d faillances arbitraires tol re aussi les arr ts francs.

Les types de d faillances pr sent s ici existent aussi bien dans les syst mes synchrones quasynchrones.

En outre, dans les syst mes synchrones, les d faillances peuvent aussi tre temporelles . Un processus

sujet des d faillances temporelles peut d faillir des mani res suivantes :

" omission g n rale ;

1. Le qualicatif byzantin vient de larticle c l bre de Lamport, Shostak et Pease The Byzantine Generals Problem

de 1982, ACM Transactions on Programming Languages and Systems, 4(3):382401, July 1982.

T l com SudParis Denis Conan Avril 2020 CSC4509

12

Arr t francOmission sur missionOmission sur r ceptionOmission g n raleArbitraire, byzantine ou maligneplus s v remoins s v re1 l ments introductifs

1.1 Mod le de syst me r parti

" d faillance de lhorloge locale : lhorloge locale d rive au del de la borne tol r e ;

" d faillance de performance : la dur e dex cution dun traitement d passe la borne tol r e ou est

trop courte. Pour un canal de communication, il sagit dune transmission trop rapide ou trop lente.

Dans ce cours, hormis lorsque nous le pr cisons explicitement dans de rares cas, les algorithmes pr sent s

sont con us dans le cas de syst mes r partis sans d faillance. En outre, les d faillances arbitraires tant tr s

diciles tol rer, le cours ne les aborde pas du tout. La tol rance aux fautes b nignes est tudi e dans les

tudes bibliographiques du module.

T l com SudParis Denis Conan Avril 2020 CSC4509

13

Initiation lalgorithmique r partie

1 l ments introductifs

$

1.2 Conventions de codage des algorithmes r partis

Notation orient e contr le

Notation orient e v nement

10

1

2

3

4

5

6

7

8

9

10

11

Chaque processus p ex cute :

var r pour tout q V oisins init F ;

begin

while #{q : r = F } > 1 do

recevoir jeton de q

r := T

mettre jeton vers q0 avec r = F

recevoir jeton de q0

r := T

decider

end

1

2

3

4

5

6

7

8

9

10

11

Chaque processus p ex cute :

var r pour tout q V oisins init F ;

var sp, dp init F ;

Sp : {#{q : r = F } = 1 and sp = F }

mettre jeton vers q0 avec r := F

sp := T

Rp : {Un message jeton est arriv }

recevoir jeton de q

r := T

Dp : {#{q : r = F } = 0 et dp = F }

decider ; dp := T

&

%

Dans les deux formes, les op rations de r ception recevoir(m) ne sp cient pas le processus metteur du

message, mais l metteur est connu apr s la r ception, cest- -dire dans la portion dalgorithme traitant la

r ception. La notation #E est utilis e pour signier la cardinalit de lensemble E. Les notations T

et F sont utilis es pour signier les valeurs bool enes vrai et faux , respectivement. Les deux

algorithmes de cette page r alisent le m me traitement, mais ce nest pas ce qui nous int resse dans cette

diapositive.

Les deux orientations (contr le et v nement) sont possibles pour chaque algorithme, mais dans de nom-

breux cas, lune est plus commode que lautre. Lorientation contr le dun algorithme consiste en un algo-

rithme s quentiel par processus avec des actions d mission et de r ception. La structure de lalgorithme est

ainsi exprim e explicitement. En revanche, le non-d terminisme est plus facilement exprim (parce quimpli-

cite) dans lorientation v nement. La sp cication consiste en une d claration de variables suivie dune liste

dactions. Chaque action consiste en une expression bool enne (laction de garde) et un bloc dinstructions

correspondantes. Laction est autoris e ou applicable lorsque la garde est valu e vrai. Dans ce cas, les

instructions de laction sont ex cut es atomiquement, cest- -dire sans interruption dans le bloc. Les actions

sont ex cut es dans nimporte quel ordre de fa on non d terministe.

T l com SudParis Denis Conan Avril 2020 CSC4509

14

Initiation lalgorithmique r partie

1 l ments introductifs

$

1.3 Relation arriv avant aussi appel e pr c dence causale,

Lamport 1978

Pr c dence causale (en anglais, happened...