[PDF] Algorithmique Distribuée L'algorithme 1 résout

View - Download Algorithmique Distribuée

Previous PDF

Next PDF

AlgorithmiqueDistribuée

StéphaneDevismes

Infospra9ques

• Contact:Stephane.Devismes@imag.fr• Web:www-verimag.imag.fr/~devismes/WWW/enseignements.html• Contactpromo:Ricm5-reseau@googlegroups.com• SallesdeCours/TD/TP,voirplanningsurADE:ade6-ujf-ro.grenet.fr/direct/

2AlgorithmiqueDistribuée

But • Algorithmesdistribués: - Spécifica9on- Concep9on- Preuvedecorrec9onetcomplexité- Implanta9on • DanslesimulateurSinalgo• Source(plug-inJava),Tutorialetsupportsdisponiblessurmapage Web • Problèmesconsidérés:briquesdebasespourlesréseaux - élec9on,circula9ondejeton,diffusion,etc. • Intérêtetinconvénient:Indépendantdel'architecture matérielle

3AlgorithmiqueDistribuée

Contenu

• 8semaines,26heures • AlternanceCours-TD/TP• Suiteducours"AlgorithmiqueDistribuée»de RICM4 • Aspect"toléranceauxfautes»

4AlgorithmiqueDistribuée

Planducours

• Rappel"Algorithmiquenontoléranteauxfautes» - 2heures • Introduc9onàlatoléranceauxfautes+bitalterné - 3heures • Consensus,impossibilité(FLP)etalgorithmes - 10heures • Auto-stabilisa9on - 11heures

5AlgorithmiqueDistribuée

Evalua9on

• Examen • 2h• Findécembre?• AnnalesdisponiblessurmapageWeb

6AlgorithmiqueDistribuée

Introduc9on

7AlgorithmiqueDistribuée

Algorithmesdistribués

8AlgorithmiqueDistribuée

Algorithmesdistribués

• AlgorithmespourdessystèmesdistribuésJ • "Eninforma9que,unsystèmedistribué(aussi

appelésystèmerépar9 )estunensembled'unitésdetraitementautonomesinterconnectéesentre-elles.»

- GérardTel,Introduc=ontodistributedalgorithms

9AlgorithmiqueDistribuée

Algorithmesdistribués

• SystèmedistribuéCWmodélisa9ondesréseaux

- Internet- Leréseaudel'Université- Leréseautéléphonique(filaire,cellulaire)- GPS- Réseaudecapteurs(surveillancesismique)- Threadssurunemachine- ...

10AlgorithmiqueDistribuée

Algorithmesdistribués

• Unitésdetraitement=processus=processeurs=noeuds

11AlgorithmiqueDistribuée

Algorithmesdistribués

• Autonome: - Chaquemachineestpourvuedesonproprecontrôle • Programmeslocaux• Mémoireslocales

12AlgorithmiqueDistribuée

Algorithmesdistribués

• Autonome: - ≠algorithmesparallèles: pasdesynchronisa9on(logicielleoumatérielle)• Asynchrone• Pasdetempsglobal

13AlgorithmiqueDistribuée

Algorithmesdistribués

• Interconnectées:échangesd'informa9ons

14AlgorithmiqueDistribuée

Algorithmesdistribués

• Interconnectées

15AlgorithmiqueDistribuée

Algorithmesdistribués

• Interconnectées:échangesd'informa9ons - viamessages

16AlgorithmiqueDistribuée

Algorithmesdistribués

• Interconnectées:échangesd'informa9ons - Couchesdecommunica9on(ModèleOSI) 17

Deuxfonc9ons:- Envoyer(M,v)- Recevoir(M,v)

U9lisateurfinal

AlgorithmiqueDistribuée

Centralisévs.Distribué

18AlgorithmiqueDistribuée

Centralisévs.Distribué

• Absencedeconnaissanceglobale - Pasd'accèsàl'étatglobaldusystème- Décisionsbaséeslamémoirelocaledunoeud

• Miseàjourenfonc9ondeséchangesd'informa9ons• Problèmedepérennitédesinforma9ons(système

asynchrone) 19

Racine=faux

AlgorithmiqueDistribuée

Centralisévs.Distribué

• Absencedetempsglobal:

- Tempsd'exécu9ondesnoeuds≠- Communica9onsasynchrones- Horlogeslocales≠(valeursini9ales≠+dérive)- Conséquence:contrairementauxsystèmes

• (Lamport1978)

20AlgorithmiqueDistribuée

Causalité:exemple

21AlgorithmiqueDistribuée

• L'événement"penvoiem»arriveavantl'événement"qreçoiem» pqm

Causalité:exemple

22AlgorithmiqueDistribuée

• L'événement"penvoiem»arriveavantl'événement"peffectuelecalculinternec» pqmc

Causalité:exemple

23AlgorithmiqueDistribuée

• Lesévénements"penvoiem»et"qenvoiem'»sontindépendants pqmm'

Centralisévs.Distribué

• Non-déterminisme - Algorithmedéterministeséquen9el:sor9es fonc9ondesentrées - Algorithmedéterministedistribué:pourles

24AlgorithmiqueDistribuée

Exemple

25AlgorithmiqueDistribuée

• Satopologie

• Sesliensdecommunica9ons• Sesprocessus• Letemps• Lesconnaissancesini9alesdesprocessussur

lesystème

AlgorithmiqueDistribuée26

27AlgorithmiqueDistribuée

Caractéris9ques

• Topologie=réseauxd'interconnexion • Topologies≈Graphe(simple)G=(V,E) - 2processusquipeuventcommuniquer directement=voisin - Communica9ons:

• bidirec9onnelles(ex.,réseauxfilaires)ou• unidirec9onnelles(ex.,réseauxàfibresop9ques)

- Généralementonsupposeradescommunica9ons bidirec9onnellesetunetopologieconnexe

28AlgorithmiqueDistribuée

Lessystèmesdistribués

• Hypothèses - Liensbidirec9onnels

AlgorithmiqueDistribuée29

Liensbidirec9onnels:pastoujours!

AlgorithmiqueDistribuée30

Rappel:Connexité

Connexe!

AlgorithmiqueDistribuée31

Rappel:Connexité

Pasconnexe!

AlgorithmiqueDistribuée32

Exemplesdetopologies

anneauarbreétoileclique

33AlgorithmiqueDistribuée

34AlgorithmiqueDistribuée

Communica9ons

• Parmessage(modèleàpassagedemessages) - Fiabilitéducanal

• (fiableouavecperteéquitableoutauxdelivraisonoudynamique)• Fiable=pasdeperte,duplica9on,créa9on

- Ordred'arrivéedesmessages • (FIFOounon) - Capacitédescanaux • (bornéoupas,borneconnueoupas) - Tempsd'acheminement(toujoursfini) • (synchrone,asynchrone,finalementsynchrone)• (pourlesdeuxderniers,borneconnueoupas) - Tempsdetraitement(supposé)négligeable

35AlgorithmiqueDistribuée

FIFO:Rappel

AlgorithmiqueDistribuée36

FIFO:Rappel

AlgorithmiqueDistribuée

A 37

FIFO:Rappel

AlgorithmiqueDistribuée

BA 38

FIFO:Rappel

AlgorithmiqueDistribuée

CBA 39

FIFO:Rappel

AlgorithmiqueDistribuée

ACB 40

FIFO:Rappel

AlgorithmiqueDistribuée

BC 41

FIFO:Rappel

AlgorithmiqueDistribuée

C 42

Tempsd'acheminement

1. Uncanalestsynchrones'ilexisteuneconstantectellequepourtou ttempst,siu nmessage estémis autempstalorsilestreçuavantletempst+couperdu.

2. Uncanalestfinalementsynchrones'ilexisteuntemps

tetuneconstantectellequepourtouttempst'≥t,siunmessage estémisautempst'alo rsilestreçu avantletempst'+couperdu.

3. Uncanalestasynchrones'iln'existepasdetempstet

43AlgorithmiqueDistribuée

44AlgorithmiqueDistribuée

Caractéris9ques

• Processus - Ini=ateur(démarrage"spontané»)ounon- - Sujetoupasauxpannes?(etqueltype?)- Asynchrone(équitable),synchroneoufinalement synchrone - Mémoirelocaledetaillebornéeounon?

45AlgorithmiqueDistribuée

46AlgorithmiqueDistribuée

Caractéris9ques

• Temps(global) - Discret:temps0,1,2...- Nonaccessibleauxprocessusmaisu9lisédansles preuves - Cependant,onu9liseraparfoisdutempslocal (minuteurs)

47AlgorithmiqueDistribuée

48AlgorithmiqueDistribuée

Caractéris9ques

• Connaissancesini>ales(entrées)desprocessus - Propriétésglobales: • Topologique:

- Topologie,e.g.,jesaisquejesuisdansunarbre- Bornesupérieureouexactesur» Lenombredeprocessus(n)» Ledegrémaximum(Δ)» Lediamètreduréseau(D)

• Dis9nc9onentrelesprocessus - Anonyme- Iden9fié- Semi-anonyme» Enraciné

49AlgorithmiqueDistribuée

Réseauxiden9fiés:Rappel

• Iden9téunique (e.g.,adresseIP)

AlgorithmiqueDistribuée

1240784216723

50

Réseauxenracinés:Rappel

51AlgorithmiqueDistribuée

Réseauxenracinés:Rappel

52

AlgorithmiqueDistribuée

Caractéris9ques

• Connaissancesini>alesdesprocessus - Propriétéslocales:connaissancesurlevoisinage

• Degrélocal?• Iden9tédesvoisins?• Numérodecanaux(é9quetagelocal)?• Rien?(ex.réseauxsansfils)

53AlgorithmiqueDistribuée

Numérota9ondescanaux

1111111222222233333344

54AlgorithmiqueDistribuée

Exemplerécapitula9f

55AlgorithmiqueDistribuée

AlgorithmiqueDistribuée56

AlgorithmiqueDistribuée57

AlgorithmiqueDistribuée58

• Entréesrépar9es

AlgorithmiqueDistribuée

59
• Entréesrépar9es • Calculslocaux - Mémoireslocales- Programmeslocals- Envoidemessages- Décisionlocale

AlgorithmiqueDistribuée

Racine=faux

60
• Entréesrépar9es • Calculslocaux - Mémoireslocales- Programmeslocals- Envoidemessages- Decisionlocale • Sor9esrépar9esAlgorithmeDistribuéExemple:Calculd'unarbrecouvrant

AlgorithmiqueDistribuée

61
• Entréesrépar9es • Calculslocaux - Mémoireslocales- Programmeslocals- Envoidemessages- Decisionlocale • Sor9esrépar9es• Tâcheglobale

AlgorithmiqueDistribuée

62

Analysedecomplexité

63AlgorithmiqueDistribuée

Complexité

• Piredescas,casmoyen,meilleurdescas • Exactouasympto9que(nota9ondeLandau)• Calculinternenégligeable

64AlgorithmiqueDistribuée

Mesuresdecomplexité

• Complexitéenmessages • Complexitéenvolume• Complexitéentemps - Tempsdetraitement=0,tempsd'acheminement=1 • Complexitéenespace(bitsouétats)

65AlgorithmiqueDistribuée

Problèmesclassiques

66AlgorithmiqueDistribuée

Problèmesclassiques

• Echangededonnée:routage,diffusion,...

• Accords:consensus,élec9on,...• Auto-organisa>on:arbrecouvrant,clustering• Alloca>onderessources:exclusionmutuelle,

dinerdesphilosophes...

AlgorithmiqueDistribuée67

Echangededonnée:routage

AlgorithmiqueDistribuée68

Echangededonnée:routage

AlgorithmiqueDistribuée

SourceDes>na>on

69

Echangededonnée:routage

AlgorithmiqueDistribuée70

AlgorithmiqueDistribuée71

Accord:élec9onCalculerunchef!

AlgorithmiqueDistribuée

4---3458567-31151-

72

Accord:élec9onCalculerunchef!

AlgorithmiqueDistribuée

4---3458567-31151-

73

AlgorithmiqueDistribuée

4---3458567-31151-1-1-1-1-1-1-1-1-1-

74

Auto-organisa>on:k-Clustering

AlgorithmiqueDistribuée75

Auto-organisa>on:k-Clustering

AlgorithmiqueDistribuée76

Auto-organisa>on:k-Clustering

• Ex.k=2

AlgorithmiqueDistribuée

77

Auto-organisa>on:k-Clustering

• Ex.k=2

AlgorithmiqueDistribuée

78

Alloca>onderessources:exclusionmutuelle

AlgorithmiqueDistribuée79

Alloca>onderessources:exclusionmutuelle

AlgorithmiqueDistribuée80

Alloca>onderessources:exclusionmutuelle

AlgorithmiqueDistribuée81

Alloca>onderessources:exclusionmutuelle

AlgorithmiqueDistribuée82

Alloca>onderessources:exclusionmutuelle

AlgorithmiqueDistribuée83

Exempletrivial:ExclusionmutuelledeLeLann

84AlgorithmiqueDistribuée

Méthodologie

1. Spécifierleproblèmeàrésoudre

2. Fixerleshypothèsessurlesystème3. Ecrireunalgorithme4. Prouverquel'algorithmevérifiela

5. Etudierlacomplexité6. Implanterl'algorithme

85AlgorithmiqueDistribuée

Spécifica9on

• Enoncéformelduproblèmequel'algorithmedoitrésoudre • Sûreté(Safety)+Vivacité(Liveness) - Sûreté:l'ensembledespropriétésquidoiventêtre - Vivacité:L'ensembledespropriétésquidoiventêtre

86AlgorithmiqueDistribuée

Spécifica9ondel'exclusionmutuelle

• accèsconcurren9elàuneressourcepartagéeuniqueviaune"sec9oncri9que»ducode - (ex.uneimprimante). DemandeurDedansDehorsRequête extérieureacquisitionlibération

87AlgorithmiqueDistribuée

Spécifica9ondel'exclusionmutuelle

• Sûreté:Auplusunprocessusestàlafois danslasec9oncri9que. • Vivacité:Toutprocessusdemandeurfinitpar entrerensec9oncri9que.

88AlgorithmiqueDistribuée

Hypothèses

• Processusetcanauxasynchrones • Pasdefautes• Topologies:anneaux unidirec9onnelavecorienta9onconsistante • Aumoinsdeuxprocessus• Unseulini9ateur• Sec9oncri9que:finie,mais nonbornée

GDGGGGGDDDDD

89AlgorithmiqueDistribuée

Syntaxegénérale

• 2primi9ves: - EnvoyeràX • Xestunnumérodecanalouuneiden9té - Récep9on depuisX • Xestunnumérodecanalouuneiden9té• VautVRAIouFAUX(récep9onnon-bloquante)

AlgorithmiqueDistribuée90

Syntaxegénérale

AlgorithmiqueDistribuée91

1Syn taxe

Algorithme1AlgorithmeApourtoutpr ocessp

1:Instructionsd'initialisation/*pasd ed´eclarati ondeva riable!*/

2:Tantquevraifaire

3:Instructions

4:Pourtoutq!V\{p}faire/*qestunnu m´erod ecanalouuneidentit´ e*/

5:Sir´ec eption"TypeMess,listevariables. ..#depuisqalors

6:Instructions

7:FinSi

8:FinPour

9:Instructions

10:Sir´ec eption"TypeMess,listevariables. ..#depuisXalors

11:Instructions

12:FinSi

13:Instructions

quotesdbs_dbs8.pdfusesText_14

[PDF] exercice corrigé algorithme matrice

[PDF] exercice corrigé ancc

[PDF] exercice corrigé anova à un facteur

[PDF] exercice corrigé antenne

[PDF] exercice corrigé arbre de défaillance pdf

[PDF] exercice corrigé architecture des ordinateurs memoire

[PDF] exercice corrigé augmentation de capital pdf

[PDF] exercice corrigé automatique asservissement

[PDF] exercice corrigé avantage comparatif

[PDF] exercice corrigé balanced scorecard

[PDF] exercice corrigé bassin versant

[PDF] exercice corrigé bassin versant pdf

[PDF] exercice corrigé bordereau d'escompte

[PDF] exercice corrigé bras de levier

[PDF] exercice corrigé budget dapprovisionnement pdf