Algorithmique des rseaux et des systmes distribus 2me A.

ISITcom
Mohamed Mosbah LaBRI ENSEIRB - Universit Bordeaux 1 mosbah@labri.fr www.labri.fr/~mosbah/Isitcom/

Objectifs du cours
Connatre les caractristiques dun systme distribu (SD) laide dalgos Comprendre les concepts et les paradigmes fondamentaux dun SD, au del (et indpendamment) des technologies Etudier certains problmes fondamentaux (lection, arbre recouvrant, exclusion mutuelle, pannes) Pouvoir raisonner dans un environnement distribu. Par exemple concevoir des applications distribues, les tester, les prouver, les valider et les implanter.

Exemples de questions aborbs dans ce cours

Comment dcrire une excution rpartie ? Comment dterminer des proprits globales partir dobservations locales ? Comment coordonner des oprations en labsence dhorloge commune ? Quelles sont les critres de qualit pour une application distribue ? Comment garantir la cohrence (ou la scurit) dinformations distribues ?
Pas sr que vous aurez toutes les rponses

 Prrequis

Faut-il des connaissances pralables ?

Connaissance de lalgorithmique lmentaire Connaissance de la programmation (java)

Ce quon ne pas voir

Comment fonctionne le tout dernier modle dIpod Comment tlcharger le tout dernier film de Spielberg Comment pirater un serveur ? ..

Organisation et site web

Planning :
20 h de cours intgr travail individuel

Site Web :
http://www.labri.fr/~mosbah/Isitcom/ Supports de cours. quelques exercices

Plan du cours
Introduction aux systmes distribus Algorithmique lmentaire (rappels), graphes, notion de complexit Modles de lalgorithmique distribue Algorithmes de diffusion, arbre recouvrant Algorithmes dElection Algorithmes de Rendez-Vous Terminaison distribue

Cours 1: Introduction aux systmes distribus

I/ Introduction linformatique distribue

Linformatique rpartie : tat de fait de plusieurs applications, et une mutation
Besoin propre des applications
Intgration : applications spares, ressources de calcul, ressources de gestion de donnes, etc Nouvelles applications: informatique omniprsente

Possibilits techniques
Interconnexion gnralise : convergence informatique-tlcom Performance et cot des machines et des rseaux

Les progrs technologiques

Avant les annes 80, les ordinateurs taient encombrants et chers (les systmes centraliss) A partir de la mi-80, deux nouveauts:
Microprocesseurs (moins chers et trs rapide) LANs and WANs

Les ordinateurs en rseaux non seulement faisables, mais simples.

Technologie + besoins
volution technologique
banalisation et capillarit des rseaux de tlcommunications performance des voies de tlcommunication (dbit et fiabilit) rapport cot/performance des stations convergence informatique et tlphonie

volution des besoins

structure des entreprises et des organisations : communication et partage (ex. Intranet) accs universel linformation (ex. Web) informatique distribue grand public (ex. vido interactive)

Applications distribues

II/ Dfinitions dun SD

Dfinition [Tanenbaum]: Un ensemble dordinateurs indpendants qui apparat un utilisateur comme un systme unique et cohrent Les machines sont autonomes Les utilisateurs ont limpression dutiliser un seul systme.

 Dfinition [Lamport]
A distributed system is one on which I cant do my work some computer has failed that I never heard of.

Un systme rparti est un systme qui vous empche de travailler quand une machine dont vous navez jamais entendu parler tombe en panne.

Dfinition (pour ce cours)

Un systme distribu est un ensemble dentits autonomes de calcul (ordinateurs, PDA, processeurs, processus, processus lger etc.) interconnectes et qui peuvent communiquer. Exemples:
rseau physique de machines Un logiciel avec plusieurs processus sur une mme machine.

Pourquoi des systmes rpartis ?

Aspects conomiques (rapport prix/performance) Adaptation de la structure dun systme celle des applications (gographique ou fonctionnelle) Besoin dintgration (applications existantes) Besoin de communication et de partage dinformation Ralisation de systmes haute disponibilit Partage de ressources (programmes, donnes, services) Ralisation de systmes grande capacit dvolution

Exemples:
WWW Contrle du trafic arien Systme de courtage Banques Super calcul distribu Systme de fichier distribu DNS Systmes Pair--pair (P2P)

Quelques domaines dapplication des systmes rpartis

CFAO, Ingnierie simultane
Coopration dquipes pour la conception dun produit Production cooprative de documents Partage cohrent dinformation

Gestion intgre des informations d'une entreprise

Intgration de lexistant

Contrle et organisation dactivits en temps rel Centres de documentation, bibliothques

Recherche, navigation, visualisation multimdia

Systmes daide la formation

Proprits
Le systme doit pouvoir fonctionner (mme en cas de pannes de certains composants), et donner un rsultat correct Le systme doit pouvoir rsister des attaques contre sa scurit (confidentialit et intgrit, dni de service, ) Le systme doit pouvoir sadapter des changements (modification de composants, sacalabilit, etc) Le systme doit prserver ses performances

III/ Objectifs dun systme distribu

Transparence (Masquer la rpartition) Uniformit des accs locaux et distants La sparation physique entre machines et les diffrences matriels/logiciels pour les accs sont invisibles par lutilisateur. Localisation des ressources non perceptible (nom logique ex: URL http://www.u-bordeaux.fr/ ) Migration des ressources possible sans interfrence avec la localisation physique (ex. transfrer un objet uniquement par son nom logique sans modification de ce nom et sans modification de lenvironnement dun utilisateur)

 Rplication de ressources non visible Concurrence daccs aux ressources non perceptible

(ex. accs un mme fichier ou une table dans une base de donnes: mcanisme de verrou ou de transaction)
- Invisibilit du paralllisme offert par lenvironnement dexcution - Tolrance aux pannes permettant un utilisateur de ne pas sinterrompre (ou mme se rendre compte) cause dune panne dune ressource

 Ouverture
Services offerts selon des rgles standards qui dcrivent la syntaxe et la smantique de ces services (Interfaces publies, ex. IDL) Interoprabilit des matriels (de fournisseurs diffrents) Portabilit Flexibilit (facilit dutilisation et de configuration) Extensibilit (ajout/MAJ de composants sans en affecter les autres)

 Mise lchelle (scalability)

fonctionne efficacement dans diffrentes chelles:
Deux postes de travail et un serveur de fichiers Rseau local avec plusieurs centaines de postes de travail et serveurs de fichiers Plusieurs rseaux locaux relis pour former un Internet

 Tolrance aux pannes

Pannes franches Pannes byzantines Dtection de pannes (difficult et mme impossibilit de dtection pour certains systmes, suspicion de machines) e.g. connexion par un navigateur un serveur distant qui rpond pas !! Correction derreurs (de fichiers/messages corrompus) Reprise sur pannes (techniques de journalisation dans les BD)

(ventuellement systme dgrad)

 Scurit
Confidentialit (authentification) Intgrit (protection contre les falsification et les corruptions) Disponibilit (accs aux ressources)

e.g. commerce lectronique, banque en ligne.

IV/ Systmes distribus vs parallles

Systmes Parallles. Une machine multiprocesseurs avec un environnement du type SIMD (tous les processeurs excutent le mme programme et ont une vision uniforme de ltat global du systme). Extensible un rseau de machines asynchrones fortement couples Systmes distribus. processus indpendants sur des machines distinctes et communiquant par change de messages asynchrones (en gnral, des rseaux faiblement coupls). Pas de consensus sur ces dfinitions

Caractristiques du paralllisme/ distribu

Objectifs: optimiser les solutions dun problme (e.g. calcul scientifique, calcul matriciel, tri) Calcul de complexit : temps et accs mmoire (pas le temps de communication ou nombre de messages) La topologie est gnralement fixe (grille, hypercube, grappes)

V/ Intergiciel (Middleware)
Le middleware (intergiciel) est la couche logicielle situe entre les couches basses (systmes d'exploitation, protocoles de communication) et les applications dans un systme informatique rparti (CORBA, EJB, COM, etc.).

 Buts:
Fournir une interface ou API de haut niveau aux applications Masquer lhtrognit des systmes matriels et logiciels sou jacents Rendre la rpartition aussi invisible (transparente) que possible Faciliter la programmation rpartie (dveloppement, volution, rutilisation, portabilit des applications)

http://www.objectweb.org/

Couches logicielles et matrielles dans un SD (le middleware)

Applications, services
APIs haut niveau

Middleware

systme dexploitation
APIs bas niveau

Rseau, matriel,

VI/ Voies dtudes des systmes distribus

Approche descriptive
Etude de modles de conception dapplications rparties (client-serveur, objets rpartis, composants rpartis, architecture) Etude de diverses classes de systmes, intergiciels (middleware) et applications, et de leurs modes dorganisation et de fonctionnement

Approche fondamentale : algorithmes distribus

Etude des principes de base: problmes fondamentaux, solutions connues, limites intrinsques Exemples : Election dun chef; Structure de diffusion (arbre recouvrant), Exclusion mutuelle, Nommage, Dtection de la terminaison

Une application pratique

Les virus sur nos machines Solution actuelle: protection individuelle (de sa machine). Limites: vulnrabilit, oubli, mise jour rgulire, solution locale mais non globale Alternative: dvelopper des stratgies globale de destruction de virus

Difficults
Pas de connaissance de ltat global Absence de temps universel (ou horloge globale) Non dterminisme (li souvent au problme du synchronisme) Et surtout pas de modle universel et standard pour lalgorithmique distribue

WiFi WiMAX ...

RceptionTV en mode IP sur PDA

Handover / mobilit

Carte p WiFi WiMAX ...

Reception TV classique Site de diffusion DVB

Zone TV Zone TV Zone TV

CarteDVB-T

Serveurd'adaptation & de diffusion

RseauLocal IP (DomaineIP) DVB Cable

RceptionTV en mode IP sur portable

1

RceptionTV DVB -T RceptionTV en modeIP

Reception TV classique+ Internet (Web +Mail)

Est-ce que ca fonctionne ? Scurit ?

Vers des modles

Modliser
pour reprsenter un systme en simplifiant divers aspect du rel pour matriser la complexit pour observer et comprendre le comportement du systme rel pour prdire ou aider commander le comportement dun systme pour prouver ce comportement laide de techniques formelles

 Ncessite de simplifier et matriser la complexit des systmes et des algorithmes distribus Difficult de lalgorithmique distribue / centralis:
Pas de connaissance de ltat global Absence de temps universel (ou horloge globale) Non dterminisme (li souvent au problme du synchronisme) Et surtout pas de modle universel et standard pour lalgorithmique distribue

Modles de communication synchrone /asynchrone Synchrone

on se voit 12h

ok on se voit 12h

Mme notion de temps, transmission instantane, gnralement borne

 Communication asynchrone:
mail: on se voit 12h 10H ok ack ok ok 10h45

11h:15 est-ce quil sait que jai lu sa rponse 12h15

11h:45 est-ce quil sait que jai ack ok

ack ack

 Communication asynchrone:
mail: on se voit 12h 10H ok ack ok ok 10h45

11h:15 est-ce quil sait que jai lu sa rponse 12h15

11h:45 est-ce quil sait que jai ack ok

ack ack

Reprsentation : abstraction
un graphe

39

A venir : Modlisation dun systme distribu

Systme distribue : graphe (non orient, connexe, simple) sommet : processus arte : canal de communication algorithme distribu local : algorithme qui sexcute sur chaque sommet (en utilisant uniquement le contexte local)

40

Les rseaux anonymes /avec identits

anonymes: pas didentits (numros distincts. e.g. IP) avec identits (chaque sommet possde un identit (un numro) unique) En gnral, il est plus facile de construire un algo sur des graphes avec identits.

41

 Ltat dun processus est cod par une tiquette: Le changement dtat : changement dtiquette Les algorithmes : arbre recouvrant, lection, terminaison, exclusion mutuelle.

42

Quelques rappels: Algorithmes, complexit, graphes

Algorithmes

Qu'est-ce qu'un algorithme? Efficacit des algorithmes

Qu'est-ce qu'un algorithme?

Un algorithme est une mthode systmatique (comme une recette) pour rsoudre un problme donn.

Exemple : calculer la somme des diviseurs de lentier n somme = 0 si n > 0 alors

Il se compose d'une suite d'oprations simples effectuer pour rsoudre un problme.

pour tout entier i entre 1 et n faire

si n est divisible par i alors ajouter i somme Finsi

En informatique cette mthode doit tre applicable par un ordinateur.

Finpour

Finsi

Pourquoi un algorithme ?
Problme

Algorithme Entre Programme Sortie

Variable A en Numrique Dbut A 34 A 12 Fin

Variable A en Numrique Dbut A 12 A 34 Fin

Lordre dans lequel les instructions sont crites va jouer un rle essentiel dans le rsultat final.

Exercice 1.1 Quelles seront les valeurs des variables A et B aprs excution des instructions suivantes? Variables A, B en Entier Dbut A1 BA+3 A3 Fin Fin corrig

Exercice 1.2 Quelles seront les valeurs des variables A, B et C aprs excution des instructions suivantes ? Variables A, B, C en Entier Dbut A5 B3 CA+B A2 CBA Fin corrig -

Exercice 1.6 Plus difficile, mais cest un classique absolu, quil faut absolument matriser: crire un algorithme permettant dchanger les valeurs de deux variables A et B, et ce quel que soit leur contenu pralable. corrig -

Importance de l'algorithmique

Pour un problme donn, il y a plusieurs algorithmes. Il est facile d'crire des algorithmes faux ou inefficaces. Une erreur peut faire la diffrence entre plusieurs annes et quelques minutes de calculs sur une mme machine. C'est souvent une question d'utilisation de structures de donnes ou d'algorithmes connus dans la littrature. Une structure de donnes est une faon particulire d'organiser les donnes.

Reprsenter et organiser les donnes

Exemple : Construire une ville de 15 maisons en vitant aux facteurs qui suivent les rues un trajet trop long depuis la poste. Organisation 1 : Linaire. Numros croissants. Poste au numro 1. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Organisation 2 : Embranchements. l'ouest de la maison k, n < k, et l'est, n > k. La poste est au numro 8. 8 12 14

11 13 15

Temps de calcul
Dans les deux organisations, le facteur a une mthode simple pour trouver une maison en partant de la poste. On suppose qu'il faut une unit de temps pour passer d'une maison une autre (en suivant une rue). Quel est, dans le cas le pire, le temps mis par un facteur pour aller jusqu' une maison depuis la poste?

Nombre de maisons 15 1023 1073741823

Temps organisation 1 Temps organisation 2 14 1022 1073741822 3 9 29

n-1

~log2(n)

Note une organisation en toile avec la poste au milieu permet des trajets trs courts, mais choisir la bonne rue prend du temps.

Temps de calcul

Le temps de calcul (ou complexit) d'un algorithme est la fonction qui un entier n associe le nombre maximal d'instructions lmentaires que l'algorithme effectue, lorsquon travaille sur des objets de taille n. En pratique, on se contente d'un ordre de grandeur. Exemples d'oprations lmentaires :

additionner, soustraire, multiplier ou diviser deux nombres, tester si une valeur est gale une autre valeur, affecter une valeur une variable.

Temps de calcul

Pour dterminer si un algorithme est efficace, on compte le nombre d'oprations ncessaire effectuer dans le pire des cas et en fonction de la taille de la donne. Le temps de calcul d'un algorithme est une valuation du nombre d'oprations lmentaires (oprations arithmtiques) qu'il effectue sur une donne de taille n. Exemple

avec l'organisation 1 de la ville, de taille n maisons, l'algorithme naturel pour trouver une maison a une complexit O(n). avec l'organisation 2 d'une ville de taille n maisons, l'algorithme naturel pour trouver une maison a une complexit O(log2(n)), ce qui est bien infrieur.

Diffrence entre n et log n

Pour notre facteur

Si n = 106, alors log2 n 20 Il fait 50 000 fois moins de dplacements si les maisons sont organiss par embranchements Si n = 109, alors log2 n 30, il fait alors 30 000 000 fois moins de dplacements.

Temps de calcul : 2me exemple

Problme : dterminer si 2 ensembles E1, E2 de n entiers ont une valeur commune. Algorithme 1 : comparer successivement chaque lment de E1 avec chaque lment de E2 ~> n2 comparaisons. 237623 =? 7363 5234 19 983 873 83889 111 9 87321

On peut rsoudre le problme avec environ nlog10(n) comparaisons!

|E1| = |E2| n 10 1000 100000 Algorithme 1 n2 100 1000000 10000000000 Algorithme 2 nlog10(n) 10 3000 500000

Diffrence entre O(n2) et O(n log(n))

Sur un ordinateur excutant une instruction lmentaire en 10-8 sec

Si les ensembles E1 et E2 ont n = 1 000 000 = 106 lments

Excuter n log10 n instructions lmentaires ncessite 0,06s. Excuter n2 instructions lmentaires ncessite 104s soit environ 2h45.

Si les ensembles E1 et E2 ont n = 10 000 000 = 107 lments

Excuter n log10 n instructions lmentaires ncessite 0,7s. Excuter n2 instructions lmentaires ncessite 106 s soit environ 11jours.

En informatique, on manipule parfois des ensembles normes

Google indexe plusieurs milliards de pages web, Google reoit prs de 200 millions de requtes/jour.

Reprsentation graphique : internet

ountry Code: from mask

Rseau pair--pair (P2P)

Reprsentation graphique : rseaux

Ll

Quelques rappels sur les graphes

Les graphes modlisent une grande varit de problmes: rseaux de communication, rseaux routiers, structures de molcules, etc On se ramne ltude de sommets et darcs. Un graphe simple G est form de deux ensembles : un ensemble V de sommets et un ensemble E dartes. Chaque arte lie deux sommets (qui sont dits adjacents ou voisins) On note G=(V,E)

Exemple

V = {u,v,w,x,y,z} E={a,b,c,d,e,f}

u a z

v d

w c x

Le degr dun graphe: f Nombre dartes adjacentes y e deg(x) = 3 Un graphe est rgulier de degr r si tous ses sommets son de degr r.

Lemme de poignes de main: Soit G=(V,E), la somme des degrs des sommets de V est le double du nombre dartes. Corollaire : un graphe simple a un nombre pair de sommets de degr impair. Application: est-il possible de relier 27 ordinateurs de sorte que chaque appareil soit reli avec exactement trois autres ?

Terminologie : graphes

Sous-graphe: G=(V,E) est sous graphe de G=(V,E) si V est sous ensemble de V et E est sous ensemble de E. Chane: suite de sommets relis entre eux par une arte. Cycle : chane qui revient son point de dpart. Graphe connexe: pour toute paire de sommets, il existe une chane qui les relie Arbre: graphe connexe sans cycle Anneau: est un graphe form dun cycle Longueur dun chane: nombre des artes qui composent la chanes Distance entre deux sommets: longueur de la plus courte chane joignant les deux sommets Diamtre dun graphe: maximum des distances entre les sommets dun graphe Mdian: un sommet qui minimise la somme des distances aux autres sommets

Les arbres

Soit G un graphe. Nous avons les quivalences suivantes:

G est un arbre Entre toute paire de nuds, il y a un seul chemin simple G est connexe, mais devient non connexe si une arte est supprime G est connexe et |E|=N-1 G est acyclique et |E|=N-1 G est acyclique, mais devient cyclique si on rajoute une arte

Arbre recouvrant

Soit G un graphe. Un arbre recouvrant de G est un sous graphe de G qui est un arbre contenant tous les sommets de G A A Exemple:
A A

Arbre recouvrant : Applications

Structure physique et logique trs utilise en informatique et rseau Construire un rseau de diffusion /

Chaque noeud reoit le message une seule fois (vite les dupplications, innodations, ..) Minimise les communications (routage efficace)

Arbres ecouvrants

Calcul dun arbre de cot minimal recouvrant un graphe connexe Applications conception de rseaux (tlphonique, lectrique, d'intercommunication,...) et tude de leur fonctionnement Algorithmes de Prim (adapt aux matrices dadjacence) de Kruskal (adapt aux listes de successeurs et graphes contenant peu dartes) O(n2) O(a log a)

Graphes non orients

G=(S, A) S sommets card S = n A artes card A = a A = {{s, t}, } s t, (pas de boucle)

chemin : ({a,b}, {b,c}, {c,d}, {d,b}, {b,a}) chemin simple : ({a,b}, {b,c}, {c,d}) cycle simple : ({a,b}, {b,d}, {d,c}, {c,a})

Chemin : c = ( {s0,s1}, {s1,s2}, , {sk-1,sk} ) o les {si-1,si} A Chemin simple les sommets intermdiaires napparaissent quune seule fois
Cycle simple

chemin simple avec s0 = sk

Sous-graphe

a
Graphe non orient G = (S, A) Sous-graphe G' G : G' graphe (S', A') avec S' S et A' A

a
Sous-graphe recouvrant si S' = S

Arbre graphe connexe sans cycle (simple) Arbre recouvrant pour G sous-graphe recouvrant qui est un arbre

Reprsentations

Matrice d'adjacence (symtrique) a b c d Listes de successeurs

(redondantes) a b c d b a a b

a 0 1 1 0

b 1 0 1 1

c 1 1 0 1

d 0 1 1 0

c c b c d d

Problme ARCM Graphe valu G = (S, A, v) avec valuation v : A R non-orient et connexe Cot dun sous-graphe G = (S, A) : (v(p,q) | (p,q) A) Problme : dterminer un ARCM, arbre recouvrant de cot minimal pour G
cot = 14 6

b
5 5 1

4 5 3

b c
2

f
3

f
3

a
6

c
3 2

a d

Les arbres recouvrants

Graphe non-orient et connexe G = (S, A) T = (S, B) arbre recouvrant pour G card S = n

Proprits T possde n-1 artes : card B = n-1 si {p, q} A-B alors H = (S, B + {u,v}) possde un cycle

b f a e d c
card S = 6 card B = 5

b f a e d c

Mthode de Prim Calcul d'un ARCM : faire grossir un sous-arbre jusqu'au recouvrement du graphe Exemple
6

b
5 5 1

4 5 3

b
5 5 1

4 5 3

b
5 5 1

4 5 3

f
3

c
2

f
3

c
2

f
3

c
2

a
6

a
6

a
6

Exemple (suite)

b
5 5 1

4 5 3

b
5 5 1

4 5 3

b
5 5 1

4 5 3

f
3

c
2

f
3

c
2

f
3

c
2

a
6

a
6

a
6

b
ARCM cot = 14

f
3

c
3 2

a d

Algorithme de Prim

arbre PRIM( graphe ({1, 2, ..., n}, A, v) ) { T {1} ; B ; tant que card T < n faire { {p, q} arte de cot minimal telle que p T et q T ; T T + {q} ; B B + {p, q} ; } retour (T, B) ; } Temps dexcution : O(n) au moyen de deux tables indexes par les sommets

Implmentation

Tables proche et cot pour trouver larte {p, q }

qT qT qT

proche[q] = p T

ssi v(p, q) = min { v(p', q) | p' T } cot[q] = v(proche[q], q) cot[q] = +

b
5 5 1

4 5 3

a c
2 proche cot

b a

c a 5

d a 3

e a 5

f a 5

f
3

a
6

Une tape
6

b
5 5 1

4 5 3

a c
2 proche cot

b a

c a 5

d a 3

e a 5

f a 5

f
3

a
6

e
6

d ajout de b et {a, b}
4 5 3

b
5 5 1

f
3

c
2

a
proche cot

b a

c b 4

d a 3

e a 5

f a 5

a
6

Temps O( 1+card A(b) )

Exemple (suite)
6

b
5 5 1

4 5 3

b
5 5 1

4 5 3

b
5 5 1

4 5 3

f
3

c
2

f
3

c
2

f
3

c
2

a
6

a
6

a
6

b
ARCM cot = 14

f
3

c
3 2

a d

Algorithme de Kruskal

Crer une fort F (un ensemble darbres) o (initialement) chaque sommet est un arbre spar. Crer un ensemble S contenant toutes les artes du graphes Tant que S est non vide

supprimer larte a de poids minimum de S Si larte a connecte deux arbres, alors la rajouter sinon lignorer

Exercice: Tester cet algo sur le graphe suivant

Graphe initial

AD et CE sont les plus courts (poids 5), choisissons AD

CE est la plus petite arte qui ne forme pas de cycle.

Ensuite DF

Complexit

Complexit de lalgorithme de Kruskal O(|E|log|E|)

Exercice

Ecrire un algorithme qui affiche les valeurs contenus dans les noeuds dun arbre ? Ecrire une fonction qui calcule le maximum des noeuds dun arbre

On utilise les notations suivantes: r: racine Pour un noeud v, pere(v) est le pre de v; Fils (v) est la liste des fils de v. Feuille(v) est une fonction qui renvoie une feuille

Parcours infix, prfix, postfix Parcours en largeur, en profondeur

Modle de lalgorithmique distribue

I/ Notion dalgorithme distribu

Un algorithme distribu sur un systme distribu S est une collection de transitions locales raliser squentiellement par chaque process de S Ces transitions peuvent seffectuer suite des vnements (internes ou change de message)

 Processus:
Les instructions dun processus sont considres comme atomiques. Il possde une mmoire locale Il possde un tat local (ensemble de ses donnes et des valeurs de ses variables locales) Il peu (ou non) avoir un identifiant Pas ou peu de connaissance des autres processus et de leur tat (il peut connaitre ltat des voisins) Il sexcute en parallle que les autres processus

 Un algorithme dsigne celui dun seul process et protocole dsigne lensemble des algos (mais on ne fait cette distinction) vnement: interne (changement dtat), envoi de message, rception de message Process p: (etati, evenmtj) (etati+1,evenmtj+1) Simulation dun mmoire partage: 1 process part qui et charg uniquement de la communication Terminaison: explicite vs implicite

II/ Modle du rseau

Process = sommet ; Canal = arte 1. Types de rseaux
A. Rseaux centraliss: Il existe un seul process dans ltat centraliseur (ou lu) et tous les autres dans ltat battu B. Rseaux avec identits: (named network) Chaque process de S est distingu par lattribution dune identit unique, distincte de tous les autres et connue par lui seul C. Rseaux anonymes: les process sont symtriques du point de vue de lexcution de lalgorithme et ne possdent pas didentits (connues deux). Ils sont indiscernables.

1. Proprits du rseau
Le graphe sous-jacent est connexe Les messages sont achemins le long des canaux. Les dlais sont finis mais non borns (peuvent tre arbitrairement longs) Les messages reus par un process sont traits dans leur ordre darrive (si en //, ordre arbitraire) Pour tout couple (pi,pj), lordre de rception des messages est le mme que celui de transmission (FIFO)

 Les tats peuvent tre cods par des tiquettes Topologie du rseau (arbre, anneau, complet,)

III/ Modle de communication (synchronisme)

1. Synchrone
horloge globale Lexcution est partitionne en rounds

(un round correspond un envoi et une rception de tous les messages. Envoi instantan ou borne fixe)
Les process ont la mme vitesse

1. Asynchrone Pas dhorloge globale Pas de borne sur le dlai de transmissions de messages Les process sont asynchrones (les horloges sont locales)

Modles de pannes
Modle de fautes : 2 grands types de fautes ou pannes
Franches : le processus ne fait plus rien Arbitraires ou byzantines : le processus renvoie des valeurs fausses et/ou fait n'importe quoi
Cas de fautes les plus complexes grer Les autres fautes peuvent tre considres comme des cas particuliers des fautes byzantines

Processus correct
Processus non plant, qui ne fait pas de fautes Dans le cas o on considre les reprises aprs erreurs et la relance de processus : processus qui pouvait tre incorrect prcdemment mais qui est correct maintenant

Fautes arbitraires / byzantines Fautes arbitraires Appeles aussi fautes byzantines Fautes quelconques et souvent difficilement dtectables Processus Calcul erron ou non fait tat interne faux Valeur fausse renvoye pour une requte Canal Message modifi, dupliqu voire supprim Message cr En pratique peu de fautes arbitraires sur les canaux car les couches rseaux assurent la fiabilit de la communication

Fautes arbitraires : classement en 2 catgories Malicieuses : erreurs volontaires (virus, attaques ...) Naturelles : problme non voulu, non dclench

IV/ Mesures de complexit Modle synchrone :

Nombre de messages : depuis le dbut jusqu la fin de lalgo. Taille dun message : complexit en nombre de bits Temps : nombre de rounds

 Modle asynchrone :
Nombre de messages Taille dun message Temps (moins vident): gnralement, on suppose que le temps de transmission sur un canal de communication mesure une unit (ou borne par une constante) Complexit en espace : espace pour un process Calcul de complexit au pire : max sur toutes les excutions possibles (gnralement le pire des excutions synchrones) Complexit moyenne : valeur moyenne de la complexit (selon une distribution de probabilits)

V/ Quelques algorithmes de base

1. Un algorithme de diffusion (Broadcast, PI)
Hypo: un arbre recouvrant donn, un message M Un sommet Pr distingu (racine) Pr envoie M tous ses fils Si un sommet reoit le message M de son pre, il lenvoie ses fils

Algo pour Pi i r receive (pere(Pi),M) pour tout fils Pj de Pi send (Pj,M)

M Pr

Exercice: Calculer la complexit en nombre de messages ? (temps) Algorithme echo ?

2. Inondation et arbre recouvrant :

un graphe G, un message M envoyer tous les sommets 2.1/ Inondation, Diffusion, PI (Propagation dInformation) Un sommet distingu (racine) P P envoie M tous ses voisins Un process Pi qui reoit M de Pj pour la premire fois, lenvoie tous ses voisins sauf Pj Exercice: Montrer que la complexit en messages est de 2m-n+1 2.2/ Application la construction dun arbre recouvrant Quand Pi reoit M pour la premire fois de Pj, il envoie Pj un message <parent> et <refus> tous les autres. Si Pj reoit <parent> de Pi alors fils(Pj) = Pi

Algorithmes de diffusion Calcul darbres recouvrants

Introduction
Etat dun process cod par une tiquette (selon son tat, les tats de ses voisins) une tape de calcul est effectu Changement dtat: rtiquetage ou relabeling Utilisation des rgles de rtiqutage Buts : Abstraction simplification facilit de preuves indpendance de tout modle implmentation unifie

Exemple
A N
N

A
N

Etape de calcul

un arbre recouvrant

Codage dalgorithmes distribus

Un sommet tiquet A (Actif), et tous les autres sont tiquets N (neutre) Rgle: Si un sommet x tiquet A possde un voisin y tiquet N Alors x est tiquet A et larte (x,y) est marque Rsultats : arbre recouvrant plusieurs rgles peuvent tre appliques en //

Preuves :
Terminaison : noethrien Correction : invariants Cet algorithme est distribu ne dtecte pas localement la terminaison globale. Dautres systmes de rcriture permettent de capturer cette proprit.

Dfinitions : systmes de rtiquetage de graphes

Un systme de rtiquetage (GRS) est un triplet R=(L,I,P) o L est un alphabet, I sous ensemble de L, P est un ensemble de rgles de rtiquetage. Chaque rgle est de la forme (Gr, r) (Gr, r), note aussi (Gr,r,r) Une tape de rtiquetage est une application dune rgle un graphe est (G,) est R-irrductible si aucune rgle de R nest applicable Systme de rtiquetage avec priorits R=(L,I,P,>) est un systme de rtiquetage avec priorits si (L,I,P) est un SR et > est un ordre partiel dfini sur lensemble P (relation de priorit). Une rgle prioritaire sapplique en 1er en cas de conflit.

 Contexte interdit: Un contexte dun graphe (G,) est un sous graphe de (G,) isomorphisme prs. Un rgle de rtiquetage avec contexte interdit est une (Gr,r,r ,Fr ) avec Fr : contexte interdit Un systme de rcriture avec contexte interdit est un systme de rcriture ou chaque rgle est avec contexte interdit Une rgle est applique sur un sous graphe sil ne contient aucun de ses contextes interdits

Application ltude des algos distribus

Ramener ltude dun algo distribu ltude dun systme de rtiquetage qui le code plus simple, facile comprendre, prouver etc. 1/ Terminaison : un algorithme distribu termine si le SR ninduit pas de chane de rcriture infinie (sil est noethrien). Pour prouver quun systme est noethrien, il suffit dexhiber un ordre noethrien compatible avec le SR: trouver un ensemble partiellement ordonn (S,<) qui na pas de chane infinie dcroissante et une fonction f : GL S / (G,) (G,) alors f(G,) > f(G,) 2/ Correction : invariants 3/ Complexit : nombre de rcritures

Exemple (Arbre recouvrant avec SR1) SR1 = (L1,I1,P1) Thorme:

1. SR1 est noethrien 2. Soit (G,) un graphe tiquet dans I1, avec un seul sommet tiquet A, et soit (G,) un graphe SR1irrductible. Le sous-graphe induit par les artes tiquetes 1 est un arbre de G. 3. La longueur dune squence est au plus n -1 (avec n le nombre de sommets de G)

SR1 est noethrien

Preuve

f : GL1 N (G, ) |VN| Lordre > sur N est compatible avec le systme de rcrirture SR1

Invariants:
P1 : Toute arte incidente un sommet tiquet N est tiquete 0 P2 : Tout sommet tiquet A ( part la racine) est incident au moins une arte tiquete 1 P3 : Le sous graphe induit par les artes tiquetes 1 est un arbre

Preuve : par rcurrence sur les chanes de rcriture

Calcul dun arbre recouvrant squentiel avec dtection de la teminaison (systme SR2)
N A M A A F

A R1 M R2

R1 > R2

 Thorme : SR2 calcule un arbre recouvrant. Il dtecte localement la terminaison globale. Preuve:
SR2 est noethrien SR2 est correct (le calcul est un arbre recouvrant)
P1: Toutes les artes incidentes N sont tiquetes 0 P2: Tout sommet tiquet A, F ou M est incident moins une arte tiquete 1 P3: le sous graphe induit par les artes tiquetes 1 est un arbre P4: il y a exactement un seul sommet tiquet A P5: le sous graphe induit par les sommets tiquets A et M et les artes tiquetes 1 est un chemin ayant une extrmit tiquete A P6: tout sommet tiquet F na aucun voisin tiquet N

Distribu avec terminaison (SR3)

A R1 A R2 A A R3 F A A N A A N A A

{
A A N A A

 Thorme: le systme SR3 calcule un arbre recouvrant avec dtection locale de la terminaison globale Preuve: SR3 est noethrien le rsultat est un arbre recouvrant dtection locale de la terminaison globale: A entoure par des F

Calculs locaux
gnralisation des SR (rcriture de boules) conditions:
C1 : ne modifie pas le graphe sous-jacent. Seul ltiquetage est modifi. C2 : ils sont locaux, chaque tape ne concerne quun sous graphe de taille fixe dans le graphe sous-jacent C3 : les rtiquetages sont localement contrls (ou engendrs); lapplication dune rgle ne dpend que du contexte local du sous graphe

Implmentation de calculs locaux.

Implmentation par des procdures Trois types de calculs locaux: computations:

1. Rendez vous : Etiquettes dun sous graphe k2 sont modifis selon des rgles qui dpendent de ces tiquettes.

Implmentation (Procdure Rendezvous). Chaque sommet excute les actions suivantes: un sommet v choisit au hasard un de ses voisins c(v); v envoie 1 c(v); v envoie 0 tous les sommets diffrents de c(v); v reoit les messages de tous ses voisins. (* Il y a un rendez-vous entre v et c(v) si v reoit 1 de c(v). Une tape du calcul peut avoir lieu*)

1. Calcul Local 1 (LC1): Pour une boule de rayon 1 (une toile), ltiquette du centre de la boule est modifie selon une rgle qui dpend de celle des sommets de la boule. 2. Calcul Local 2 (LC2): Comme pour LC1sauf que tous chaque sommet de la boule modifie son tiquette. Implmentation de LC1( Election locale probabiliste): Le sommet v tire au hasard un entier rand(v); v envoie rand(v) tous ses voisins; v reoit les entiers de ses voisins; (* le sommet v est lu dans B(v,1) si rand(v) est strictement plus grand que tous les entiers reus par v; dans ce cas un pas de calcul LC1 peut tre effectu sur B(v,1) *)

Implmentation de LC2( Election locale probabiliste): Le sommet v tire au hasard un entier rand(v); v envoie rand(v) tous ses voisins; v reoit les entiers de ses voisins; v envoie le max des entiers reus chacun de ces voisins; v reoit les entiers de ses voisins. (* le sommet v est lu dans B(v,2) si rand(v) est strictement plus grand que tous les entiers reus par v; dans ce cas un pas de calcul LC2 peut tre effectu sur B(v,1) *)

LE1

LE2

Un mta-algorithme
Chaque processeur excute While (run){ \\ Synchronisation (rendezvous, LE1, LE2); \\ Echange dtiquettes, attributs, \\ calculs; \\ Mise jour des tiquettes, attributs, tats; \\ Arrt de la Synchronisation; }

Exemple (Calcul dun arbre recouvrant Rendezvous)

while (run) { neighbour = rendezVous(); sendTo(neighbour,myLabel); neighbourLabel=receiveFrom(neighbour); if (myLabel == 'N') && (neighbourLabel == 'A'){ myLabel = 'A'; edge[neighbour]=1 } breakSynchro(); }

Application la visualisation de lexcution dun algorithme distribu

Implmentation la visualisation de tous les vnements. Bibliothque de primitives. Les proprits du systme de rcriture sont prserves: : consistance, ordre des vnements, terminaison, rsultats.

ViSiDiA
Un environnement pour simuler, visualiser et exprimenter les algorithmes distribus. Un processeur est implment par un thread Java. Une bibliothque de primitives de haut niveau est disponible pour le programmeur. Une interface graphique (contrlable par lutilisateur) permet lutilisateur de
1. Construire dditer un rseau (avec GML export/import). 2. visualiser lexcution dun algorithme ou de lexprimenter.

Architecture

Modulaire, orient-objet, portable, interactif, limites (celles de la java)..

Algorithmes dElection

Election
Chaque process dcide sil est lu ou non Rsultat de lalgo: - un seul sommet au lu - tous les autres non lus Applications :
un algorithme centralis doit tre excut dans un environnement distribu aprs un crash Sauvegarde des ressources

Une classe de problmes pour briser la symtrie

Dfinitions : un algorithme dlection est un algorithme qui satisfait les proprits suivantes: chaque processeur excute le mme algo. local lalgorithme est dcentralis, i.e. le calcul peut tre initialis par un sous ensemble de process lalgorithme termine dans tout calcul, et la configuration terminale
un seul lu (ou leader) tous les autres : non lu (ou perdant)

Election dans un anneau

Etat initial Etat final leader

Election dans les anneaux anonymes

Les processeurs dun anneau anonyme ne possdent pas didentifiants uniques (utiliss par lalgorithme) Tous les processeurs sont symtriques (ils envoient les mmes messages, ils reoivent les mmes rponses, ils sont dans le mme tat) Il nexiste pas dalgorithmes dlection dans un anneau anonyme (dans un modle synchrone)

Etat initial

Etat final leader

Si un noeud est lu, alors tout noeud est lu

De mme pour le modle asynchrone

Anneau avec identits

Le noeud avec id max est lu 1 5 6 3 7 4 8 2

Chaque noeud envoie un message contenant Son id au voisin suivant 1 5 5 3 3 7 7 4 4 1 8 8 2 2 6 6

Si: id recu est > id courant alors: faire passer id 5 8 2 8 6 3 7 6 4

1 5 7

Si: id recu est > id courant alors: faire passer id 8 2 6 3 7 4 8

7 5

Si: id recu est > id courant alors: faire passer id 7 1 5 6 3 7 8 4 8 2

Si: id recu est > id courant alors: faire passer id 8 2 6 3 8 7 4

1 5

Si: id recu est > id courant alors: faire passer id 8 1 5 6 3 7 4 8 2

Si:

un noeud reoit son propre id

alors: il est lu 8 leader

1 5

2 6

3 7

Le leader envoie un message au rseau pour informer quil est lu 8 leader

1 5

2 6

3 7

Complexit temps: Remarque:

O ( n)
8 leader

noeuds

peut ne pas tre connu par lalgo 1

2 6

3 7

Exercice: Soit un anneau avec des identits de sommets numrots de 1 n. Quel est la configuration de lanneau qui reprsente le pire des cas pour le nombre de messages ?

complexit messages: O ( n 2 ) Pire cas:

n
n

noeuds

1 2

n-1

n-2 n-3

complexit messages: O ( n 2 )

n
n

noeuds

messages 2

n-1

n-2 n-3

complexit messages: O ( n 2 )

n
n

noeuds

n 1

messages 2

n-1

n-2 n-3

complexit messages: O ( n 2 )

n
n

noeuds

n 2 messages
2

n-1

n-2 n-3

complexit messages: O ( n 2 ) Nbre total messages:

n
n

noeuds

n+

n 1+
n 2+ 2+ 2 1 = O(n )
2

n-1

n-2 n-3

Un algorithme O(n log n)

Election du noeud avec id maximal 1 5 6 3 7 4 8 2

k voisin k
noeuds 1 5 6 3 7 4 8

k
2

noeuds

Phase 1:

envoyer id aux 1-voisins 1 5 5 3 1 1 5 3 7 3 7 7 4 8

8 2

8 2 6 4 6 4 6 2

Si: id recu > id courant alors: envoyer une rponse 1 5 6 3 7 4 8 2

Si: un oeud recoit les deux rponses alors: le noeud devient un leader local 1 5 6 3 7 4 8 2

Phase 2: envoyer id aux 2-voisins 8 1 5 5 3 7 7 7 5

8 8 2 6 6 4 6

Si: id recu > id courant alors: faire passer le message 8 5 6 2 8 6 3 5 7 6 4 7

8 5 7

Seconde tape: Si: id recu > id courant alors: envoyer une rponse 1 5 6 3 7 4 8 2

Si: un noeud recoit deux rponses alors: il devient leader temporaire 1 5 6 3 7 4 8 2

Phase 3:

2 envoyer aux 2 -voisins

8 5

1 7 3 7

8 2 7 4 8 6

Si: id recu > id courant alors: faire passer the message 8 2 7 4 8 6

8 5

1 7 3 7

A ltape: 2 2 Si: id recu > id courant alors: envoyer une rponse 1 5 6 3 7 4 8 2

Si: un noeud recoit les deux rponses alors: il devient leader 1 5 6 3 7 4 8 2

1 5

8 leader

2 6

3 7

En gnral:

noeuds 1 5

log n
8 leader 2

phases

Phase i:

envoyer id au i 1 1 5

i 1

-voisins

8 leader

2
6

i 1

Complexit en temps Le cot du calcul du leader en temps Phase Phase Phase Phase Total : 1: 2 2: 4 i:

i log n

log n: 2

log n + 1

2 = O(2

log n

) = O ( n)

complexit en messages Nombre de messages par leader Phase Phase Phase Phase 1: 2 2: 4 i: leaders

n/2 n/4 n/2

log n i

log n: 2

n/2

log n

Nombre de messages par leader Phase Phase Phase Phase 1: 2 2: 4 i:

leaders

log n

n/2 n/4 n/2 n/2

i

= n = n = n = n

log n: 2

log n

Nbre de messages:

O (n log n)

Formulation laide des systmes de rcriture

On dit quun SR rsoud le problme dlection pour une classe de graphes C si il est nothrien Il existe deux labels N et T / pout tout G dans C, initialement tiquet N, si (G,) tel que Irred (G, ) alors il existe exactement un sommet v dans V(G) tiquet T, (v) = T

A/ Election dans un arbre

A.1/ Election dans un arbre.
N R1 N N F N N N

{
N E N

} }

R2

{
N

Implmentation de llection dans un arbre

while(run){ synchro=starSynchro1(); Si( synchro==starCenter ){ int n_Count=0; for (int door=0;door<arity;door++) { neighbourState[door]=receiveFrom(door); Si (neighbourState[door]=="N") n_Count++; } Si ((myState="N") && (n_Count ==1)) changeState(F); else Si ((myState=="N") && (n_Count==0)) { changeState(E); run=false; } breakSynchro(); } else { Si (synchro == starLeaf) { sendTo(center,myState); } } } /* demo */

A.2/ Election dans un graphe complet

N R1

R2

{
N

Implmentation de llection dans un graphe complet while(run){ neighbour=rendezVous(); sendTo(neighbour,myState); neighbourLabel=receiveFrom(neighbour); Si ((myState == "N") && (noNeighbourN)) myState ="E" Si ((myState == "N") && (neighbourLabel== "N")) { myState="F"; } }

Election dans un anneau avec identits

(id1,x) R1 (id2,y) (id1,x) (id2,x) (id2,y) (id1,x) (id2,x)

x>y
si x = id2

(id1,x) R1

- Initialement : (i,i) - garder la plus grande identit