[PDF] Silence dans la forêt! 3 mai 2019 La dé

View - Download Silence dans la forêt!

Previous PDF

Next PDF

>G A/, ?H@ykRR389N ?iiTb,ff?HXb+B2M+2f?H@ykRR389Npk aBH2M+2 /Mb H 7Q`i5 hQ +Bi2 i?Bb p2`bBQM,

Silence dans la for

ˆet !†

Karine Altisen

1, St´ephane Devismes1et Ana¨ıs Durand2

1 Univ. Grenoble Alpes, CNRS, Grenoble INP, VERIMAG, 38000 Grenoble

2Sorbonne Universit´e, CNRS, Inria, LIP6, F-75005 Paris, FranceNous formalisons des sch

´emas d"algorithmes distribu´es, classiquement utilis´es en autostabilisation, afin d"obtenir des

r

´esultats g´en´eraux relatifs`a leur correction et leur complexit´e. Pr´ecis´ement, nous´etudions une classe d"algorithmes

d

´edi´es aux r´eseaux munis d"un sens de direction d´ecrivant une forˆet couvrante. La d´efinition de cette classe est simple

au sens o

`u elle est quasi-syntaxique. Tous les algorithmes de cette classe sont (1) autostabilisants et silencieux, et (2)

ont un temps de stabilisation `a la fois polynomial en mouvements et asymptotiquement optimal en rondes. Pour illustrer la polyvalence de notre m ´ethode, nous passons en revue plusieurs travaux o`u nos r´esultats s"appliquent. Mots-clefs :autostabilisation, silence, arbres, forˆets1 Introduction

L"autostabilisationest une propri´et´e caract´erisant une aptitude d"un syst`eme distribu´e`a tol´erer desfautes

transitoires. Les fautes transitoires sont rares, de dur´ee finie et affectent l"´etat du composant du r´eseau

(processus ou lien) o `u elles surviennent. La corruption de la m´emoire locale d"un processus ou du contenu `esunnombrefinidefautestransitoires de lui-m ˆeme et en temps fini un comportement correct, c"est-`a-dire conforme`a sa sp´ecification.

Contexte.Les forˆets et arbres couvrants sont omnipr´esents en autostabilisation. Par exemple, on retrouve

souvent ces structures de donn ´ees dans lacompositiond"algorithmes. La composition [2] est une m´ethode modulaire, usuelle en autostabilisation, permettant de simplifier `a la fois la conception et les preuves d"al-

gorithmes. De nombreux algorithmes autostabilisants sont conc¸us comme une composition entre un algo-

rithme de construction de for ˆet ou d"arbre couvrant et un algorithme d´edi´e aux topologies arborescentes (arbres ou for

ˆets). De multiples algorithmes autostabilisants efficaces de construction d"arbre ont d´ej`a´et´e

propos

´es,cf.l"´etat de l"art propos´e par G¨artner [6]. La majorit´e d"entre-eux sont aussi silencieux. Un algo-

rithmesilencieuxconverge vers une configuration diteterminale`a partir de laquelle les valeurs des variables

de communication des processus ne changent plus. Nous nous int

´eressons ici aux algorithmes autostabili-

sants utilisant une structure arborescente, par exemple, calcul

´ee par l"un de ces algorithmes dans le cadre

d"une composition. De mani `ere g´en´erale, les algorithmes d´edi´es aux structures arborescentes sont fond´es (quasiment uniquement) sur des approches ascendantes (bottom-up) et/ou descendantes (top-down).

Contribution.Nous formalisons ici ces pratiques usuelles pour en faire un r´esultat syst´ematique. Nous

d

´efinissons dans le mod`ele`a´etats (le mod`ele de calcul commun´ement utilis´e en autostabilisation), une

classe d"algorithmes, d ´edi´es aux r´eseaux munis d"un sens de direction d´ecrivant une forˆet couvrante, et

utilisant des approches ascendantes et descendantes.´Evaluer l"appartenance d"un algorithme`a cette classe

est quasi-syntaxique. Ses algorithmes sont autostabilisants et silencieux sous l"hypoth `ese d"un d´emon dis- tribu

´e in´equitable, l"hypoth`ese d"ordonnancement la plus g´en´erale du mod`ele. De plus, ils sont efficaces en

temps de stabilisation,i.e., la dur´ee maximale avant que l"algorithme retrouve un comportement correct,

puisque celui-ci est polynomial en mouvements et asymptotiquement optimal en rondes. Le challenge a

´et´e

d"obtenir un compromis entre efficacit

´e et g´en´eralit´e. En effet, plus la classe consid´er´ee est g´en´erale, plus il

est difficile de prouver des bornes de complexit ´e fines pour tous les algorithmes de la classe.†

Cette´etude a´et´e financ´ee par les projets ANR DESCARTES (ANR-16-CE40-0023) et ESTATE (ANR-16-CE25-0009).

Karine Altisen, St

´ephane Devismes et Ana¨ıs Durand

Plan.Dans la section suivante, nous d´ecrivons rapidement le mod`ele`a´etats ainsi que quelques notions et

notations utilis

´ees dans le reste de l"article. Dans la section 3, nous pr´esentons notre classe d"algorithmes

ainsi que les r

´esultats de complexit´e obtenus pour cette classe. Nous illustrons notre d´efinition avec un

exemple jouet montrant que la condition d"appartenance `a cette classe est simple`a´evaluer. Par manque de place, toutes les preuves de nos r ´esultats sont omises (elles sont disponibles dans l"article [1]). Nous `unosr´esultatss"appliquent. 2 Mod `ele

Nous consid

´erons des r´eseaux bidirectionnels asynchrones connexes denprocessus o`u chaque processus peut communiquer directement avec un sous-ensemble d"autres processus appel

´esvoisins. On noteVl"en-

semble des processus. Ces r ´eseaux sont munis d"un sens de direction : chaque processuspposs`ede deux entr

´ees constantesp:p`ereetp:enfs. Lorsquep:p`ere=?,pest appel´eracine. Dans le cas contraire,p:p`ere

d

´esigne un voisin appel´e le p`ere dep. La constantep:enfsest l"ensemble des enfants dep, c"est-`a-dire les

voisins le d ´esignant comme p`ere. Sip:enfs=/0, alorspest unefeuille. Nous supposons que le sous-graphe orient ´e induit par les pointeurs p`eres est une forˆet couvrante du r´eseau.

Le mod

`ele`a´etats est une abstraction du mod`ele`a passage de messages dans lequel les´echanges d"infor-

mations sont r

´ealis´esviadesvariables localement partag´ees: chaque processus d´etient un nombre fini de

variables dans lesquelles il peut lire et ´ecrire; de plus, il peut lire les variables de ses voisins dans le r´eseau. L"

´etatd"un processus est d´efini par la valeur de ses variables. Laconfigurationdu syst`eme est d´efinie par

l"

´etat de chacun de ses processus. Un algorithme distribu´e est un ensemble denalgorithmes locaux, un

par processus, o `u chaque algorithme local consiste en un ensemble fini de r`egles. Chaque r`egle est de la

formeEtiquette::Garde!Actiono`u l"´etiquette identifie la r`egle, sa garde est un pr´edicat bool´een sur les

variables du processus et de ses voisins, et l"action est un ensemble d"affectations modifiant l"

´etat du pro-

cessus. L"ex

´ecution d"un algorithme distribu´e est compos´ee d"une succession d"´etapes atomiquesde calcul.`A chaque´etape de calcul, chaque processus d´etermine en fonction de son´etat et de celui de ses voisins

s"il estactivable, c"est-`a-dire si la garde d"au moins une de ses r`egles est vraie. Un adversaire, led´emon,

choisit ensuite un sous-ensemble non vide de processus activables. Les processus choisis sont alorsactiv´es:

ils effectuent unmouvemento`u ils ex´ecutent atomiquement la partie action d"une de leur r`egles activables.

Nous supposons ici que les processus sont activ

´es de mani`ere asynchrone sans hypoth`ese particuli`ere sur l"

´equit´e (le d´emon estdistribu´e in´equitable). S"il n"y a pas de processus activables, l"ex´ecution se termine

et la derni `ere configuration est diteterminale.

Le temps de stabilisation d"un algorithme est g

´en´eralement exprim´e selon deux types de mesures : le

nombre demouvementset derondes. La premi`ere ronde d"une ex´ecution termine d`es lors que tous les

processus qui

´etaient continˆument activables depuis le d´ebut de l"ex´ecution ont ex´ecut´e au moins une r`egle.

La seconde ronde commence

`a la fin de la premi`ere,etc.

3 Notre r

´esultat

Nous consid

´erons maintenant un algorithme distribu´e quelconqueAet sa sp´ecification sous la forme d"un pr

´edicatSPsur les configurations. Notre principal r´esultat est le th´eor`eme 1. Les notions et notations

utilis

´ees dans ce th´eor`eme seront d´efinies et illustr´ees avec un exemple jouet dans la suite de la section.

Th

´eor`eme 1SiAsuit une strat´egie acycliqueet toute configuration terminale deAsatisfait SP alors

-Aest autostabilisant et silencieux pour SP; - son temps de stabilisation en mouvements est born

´e par1+d(1+D)HknH+2; et

- siAest (en plus) localement mutuellement exclusif, alors son temps de stabilisation en rondes est au

plus(H+1)(H+1); o

`uDest le degr´e du r´eseau, H est la hauteur de la forˆet couvrant le r´eseau,Hetdsont respectivement la

hauteur et le degr ´e entrant du graphe ditde causalit´eGC, et k est le nombre de familles deA. Notez queH,detksont quasiment toujours des constantes ind´ependantes de la taille du r´eseau.

3.1 Un exemple illustratif

Dans la suite, nous proposons d"

´etudier un algorithme simple, not´eT E, fonctionnant dans un r´eseau en arbre orient ´e enracin´e enr. Le but de cet algorithme est de calculer la somme des entr´ees de chaque

Silence dans la for

ˆet !

processus et de diffuser ce r ´esultat`a l"ensemble des processus du r´eseau. Ainsi, chaque processuspd´etient une entr ´ee constante enti`erep:E2N. Ensuite,pmaintient deux variables :p:sub2N- dans laquellep calcule la somme des entr ´ees de ses descendants dans l"arbre - etp:res2N- la sortie de l"algorithme qui devra finalement contenir la somme de toutes les entr

´ees. Le but deT Eest donc de converger vers

une configuration terminale v ´erifiant le pr´edicatSomme8p2V;p:res=åq2Vq:E. Pour cela,T Eest d

´efini par les r`egles suivantes.

Pour tout processusp:S(p)::p:sub6= (åq2p:enfsq:sub)+p:E!p:sub:= (åq2p:enfsq:sub)+p:E

Pour la raciner:R(r)::r:res6=r:sub!r:res:=r:sub

Pour tout processusp6=r:R(p)::p:res6=max(p:p`ere:res;p:sub)!p:res:=max(p:p`ere:res;p:sub)

3.2 Strat

´egie acyclique

D

´efinition :Asuit unestrat´egie acycliquesi (1)Aestbien form´e, (2) songraphe de causalit´eGCest sans

circuit, et (3) pour toutefamille de r`egles Aide sapartition familiale,Aiestponctuelleet soitdescendante,

soitascendante. Nous explicitons maintenant, les notions employ´ees dans cette d´efinition.

Famille de r

`egles bien form´ee.Tout d"abord, nous appelonsfamille de r`egles Aiun ensemble denr`egles o

`u chaque r`egle appartient`a un processus diff´erent. On noteraAi(p)la r`egle du processuspappartenant`a

la familleAi.

Un algorithme distribu

´e estbien form´esi ses r`egles peuventˆetre partitionn´ees en famillesA1, ...,Ak, appel

´eespartition familiale, telles que8i2 f1;:::;kg, les variables´ecrites (donc non-constantes) par les

r `egles deAiont le mˆeme nom. DansT Enous avons deux familles :S=fS(p)jp2Vg(qui´ecrit dans les

variablessub) etR=fR(p)jp2Vg(qui´ecrit dans les variablesres). Il faut plutˆot comprendre la propri´et´e

bien form´ecomme une norme d"´ecriture permettant de simplifier l"analyse de l"algorithme.

Graphe de causalit

´e.Nous supposons maintenant queAest bien form´e. SoientA1, ...,Akla partition

familiale deA. On d´efinit la relation binaireAsur les familles deAcomme suit :AjAAisi et seulement

sii6=jet il existe au moins deux processuspetqtels que la r`egleAj(p)´ecrit dans des variables lues par

A

i(q),i.e., apparaissant dans sa garde. PourT E, on aST ER. Nous repr´esentons ensuite cette relation

sous la forme d"un grapheGCappel´e graphe decausalit´e:GC=(fA1;:::;Akg;f(Aj;Ai)jAjAAig). Pour T E,GCconsiste simplement en l"unique arcS!R, en particulier iciGCest sans circuit.

Famille de r

`egles ponctuelle.Une famille de r`eglesAiestponctuellesi pour tout processusp, la r`egle A

i(p)devient inactivable`a chaque fois queAi(p)est ex´ecut´ee et qu"`a part les variables´ecrites parAi(p),

aucune autre variable lue parAi(p)n"est modifi´ee. Il s"agit du seul crit`ere non syntaxique pour´evaluer si

l"algorithme suit une strat ´egie acyclique. Les deux familles deT E,SetR, sont ponctuelles car les actions de leur r `egles rendent leurs gardes fausses.

Famille de r

`egles descendante/ascendante.Intuitivement, une famille de r`eglesAiestdescendantesi ses r

`egles sont uniquement propag´ees vers le bas dans la forˆet,i.e., quand la r`egleAi(q)est ex´ecut´ee, elle

ne peut rendre activable des r `egles de sa familleAiqu"au niveau de ses enfants. Dans ce cas,Ai(q)´ecrit dans certaines variables lues par des r `eglesAi(p)de ses enfants, ces variables pouvantˆetre compar´ees aux variables ´ecrites parAi(p)elle-mˆeme. Ainsi, une famille de r`eglesAiestdescendantesi pour tout processusp, pour toute variableq:vlue parAi(p),q:vest´ecrite parAi(q)seulement siq=pouq=p:p`ere.

Similairement, une famille de r

`eglesAiestascendantesi pour tout processusp, toute variableq:vlue parAi(p),q:vest´ecrite parAi(q)seulement siq=porq2p:enfs. DansT E,Sest ascendante etRest descendante.

3.3 Complexit

´e en mouvement deT E

Nous avons vu que l"algorithme distribu

´eT Esuit une strat´egie acyclique. De plus, par induction, nous pouvons facilement d ´emontrer que toute configuration terminale deT Esatisfait le pr´edicatSomme.

Ainsi, d"apr

`es le th´eor`eme 1,T Eest autostabilisant et silencieux sous l"hypoth`ese d"un d´emon distribu´e

in ´equitable. De plus, puisqueH=1,d=1 etk=2, le temps de stabilisation en mouvements deT Eest

au plus(4+2D)n3. En utilisant un lemme interm´ediaire, aussi propos´e dans notre article [1], cette borne

Karine Altisen, St

´ephane Devismes et Ana¨ıs Durand

peut

ˆetre affin´ee pour obtenir un temps de stabilisation d"au plus(3+2H)n2mouvements. Cette derni`ere

complexit ´e est pr´ecise car nous avons aussi prouv´e qu"elle´etait atteignable sur des exemples.

3.4 Complexit

´e en rondes deT E

Malheureusement suivre unestrat´egie acycliquen"est pas suffisant pour garantir des bornes int´eressantes

en nombre de rondes. Dans notre article [1], nous montrons l"existence d"un pire des cas enW(n)rondes

pourT Elorsque le r´eseau est un arbre de hauteur 1! Comme le sugg`ere le th´eor`eme 1 cela est dˆu au fait

que les famillesSetRdeT Ene sont pas localement mutuellement exclusives (n.b., ce crit`ere n"est pas

syntaxique). En effet, deux famillesAietAjsont localement mutuellement exclusives si pour tout processus

p, on ne peut jamais avoirAi(p)etAj(p)activables simultan´ement. Or, dansT E, les r`eglesR(p)etS(p)

d"un m ˆeme processusppeuventˆetre activables dans la mˆeme configuration.

Notre th

´eor`eme montre que si un algorithme suit une strat´egie acyclique et est localement mutuellement

exclusif (c"est- `a-dire, les familles qui le constituent sont deux`a deux localement mutuellement exclusives)

alors(a)il est autostabilisant,(b)sa complexit´e en mouvements est polynomiale et(c)sa complexit´e en

rondes est dans la majorit ´e des cas asymptotiquement optimale (en effet,kest g´en´eralement une constante).

Nous avons aussi propos

´e une transformation simple permettant de rendre localement mutuellement ex- clusif tout algorithme suivant une strat ´egie acyclique. Cette m´ethode ne d´egrade pas la complexit´e en mou- vement de l"algorithme `a transformer. Elle consiste simplement`a ajouter des priorit´es aux r`egles de l"algo- rithme. Ces priorit ´es suivent n"importe quel ordre total compatible avecA. Pour r´ealiser ces priorit´es, il suffit d"ajouter `a la garde de chaque r`egle de chaque processuspla n´egation de la disjonction des gardes des r

`egles depplus prioritaires. Ainsi, aucune r`egle depne peut plusˆetre activable en mˆeme temps qu"une

autre r

`egle depplus prioritaire. Par exemple, pourT E, il suffit d"ajouter la n´egation de la garde deS(p)

a la garde deR(p)pour tout processusp. Ainsi, nous obtenons un nouvel algorithme autostabilisant pour

Sommequi stabilise en au plus 2H+2 rondes et au plus(4+2D)n3mouvements.

4 Conclusion

Nous avons

´etudi´e la correction et la complexit´e d"un sch´ema d"algorithmes distribu´es, classiquement

utilis

´es en autostabilisation, d´edi´e aux r´eseaux munis d"un sens de direction d´ecrivant une forˆet couvrante.

Nos r

´esultats permettent de d´eduire ais´ement (i.e., quasi-syntaxiquement) des bornes fines sur le temps de

stabilisation en mouvements et en rondes de ces algorithmes. Nous avons identifi

´e plusieurs algorithmes de

la litt

´erature,e.g., [8, 4, 3, 7], o`u s"applique notre sch´ema. Pour plusieurs de ces travaux (e.g., [4, 7]), notre

approche permet de d

´eduire la stabilisation de l"algorithme sous des hypoth`eses plus g´en´erales, c"est-`a-dire,

sous l"hypoth

`ese d"un d´emon distribu´e in´equitable. Dans certain cas (e.g., [8, 3]), nous exhibons une borne

de complexit

´e (en mouvements ou en rondes) alors qu"elle n"avait pas´et´e´etudi´ee dans l"article original.

Dans la plupart des articles, l"hypoth

`ese de l"existence d"une forˆet couvrante est une hypoth`ese in- term

´ediaire puisque cette derni`ere est construite par un algorithme sous-jacent. Il existe de nombreux algo-

rithmes autostabilisants efficaces (en mouvements et en rondes),e.g.[5], permettant de construire de telles

structures. La composition des instances de notre sch ´ema avec ces derniers doitˆetre attentivement abord´ee afin d"obtenir un algorithme combin

´e efficace.

R

´ef´erences

[1] K. Altisen, S. Devismes, and A. Durand. Acyclic strategy for silent self-stabilization in spanning forests. InSSS"18, pages

186-202, 2018.

[2] A. Arora, M. Gouda, and T. Herman. Composite routing protocols. InSPDP"90, pages 70-78, 1990.

[3] P. Chaudhuri. AnO(n2)self-stabilizing algorithm for computing bridge-connected components.Computing, 62(1) :55-67, 1999.

[4] P. Chaudhuri and H. Thompson. Self-stabilizing tree ranking.Int. J. Comput. Math., 82(5) :529-539, 2005.

[5] S. Devismes, D. Ilcinkas, and C. Johnen. Silent Self-Stabilizing Scheme for Spanning-Tree-like Constructions. InICDCN"19,

pages 158-167, 2019. [6] F. C. G

¨artner. A survey of self-stabilizing spanning-tree construction algorithms. Technical report, EPFL, 2003.

[7] M. H. Karaata. A self-stabilizing algorithm for finding articulation points.Int. J. Found. Comput. Sci., 10(1) :33-46, 1999.

[8] V. Turau and S. K

¨ohler. A distributed algorithm for minimum distance-k domination in trees.J. Graph Algorithms Appl.,

19(1) :223-242, 2015.

quotesdbs_dbs41.pdfusesText_41

[PDF] un petit paragraphe sur la foret

[PDF] définition d'une foret

[PDF] revenir en france apres avoir vecu a l'etranger

[PDF] retour en france des français de l'étranger

[PDF] simulateur retour en france

[PDF] declaration impot retour expatriation

[PDF] format 16/9 photoshop

[PDF] format 16/9 en cm

[PDF] format 4/3 résolution

[PDF] resolution ecran 16/9

[PDF] format 16/9 indesign

[PDF] format 4/3 en cm

[PDF] format 4/3 photo

[PDF] format 16/9 en px

[PDF] code urssaf dsn