Algorithmes distribués

Cyril Gavoille

Description

Introduire l’algorithmique distribuée ; concevoir et analyser des algorithmes distribuées.

Informations

• Publié par: Force_IT
• Nombre de lectures: 34
• Licence : En savoir +
  Paternité, pas d'utilisation commerciale, partage des conditions initiales à l'identique
• Langue: Français
• Poids de l'ouvrage: 2 Mo

Extrait

Algorithmes distribuÉs

Cyril Gavoille LaBRI Laboratoire Bordelais de Recherche en Informatique, UniversitÉ de Bordeaux [e-mail]

13 fvrier 2014

2

Algorithmes distribuÉs – Master 1 & 2 –

Objectifs :Introduire l’algorithmique distribue; concevoir et analyser des algorithmes distribues (M2); prsenter diffrentes applications et problmatiques actuelles; program- mer des algorithmes sur un simulateur/visualisateur de calcul distribu (M1).

Pr-requis :Algorithmique ;notions de thorie des graphes

Rfrences :

Distributed Computing : A Locality-Sensitive Approach, David Peleg SIAM Monographs on Discrete Mathematics and Applications, 2000

Distributed Graph Coloring : Fundamentals and Recent Developments, Leonid Barenboim and Mickael Elkin Morgan & Claypool, 2013

Design and analysis of distributed algorithms, Nicola Santoro Wiley Series on Parallel and distributed computing, 2006

Introduction to Distributed Algorithms (2nd Edition), Gerard Tel Cambridge University Press, 2000

Table des matiÈres

1 Introduction7 1.1 Qu’estce que le calcul distribu ?. . . . . . . . . . . . . . . . . . . . . . .7 1.2 Uncadre de base pour les systmes distribus. . . . . . . . . . . . . . . .8 1.3 Spcificitsdu calcul distribu. . . . . . . . . . . . . . . . . . . . . . . . .10 1.3.1 Lescommunications10. . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.2 Connaissancepartielle12. . . . . . . . . . . . . . . . . . . . . . . . . 1.3.3 Erreurset dfaillances13. . . . . . . . . . . . . . . . . . . . . . . . . 1.3.4 Synchronisme13. . . . . . . . . . . . . . . . . .. . . . . . . . . . . . 1.3.5 Non-dterminisme. . . . . . . . . . . . . . . . . . . . . . . . . . . .14 1.4 Surles algorithmes distribus. . . . . . . . . . . . . . . . . . . . . . . . .14

2 Complexitset modles17 2.1 Mesuresde complexit. . . . . . . . . . . . . . . . . .. . . . . . . . . . . 17 2.2 Modlesreprsentatifs19. . . . . . . . . . . . . . . . . .. . . . . . . . . . . 2.3 Rappelssur les graphes. . . . . . . . . . . . . . . . . .. . . . . . . . . . . 20 2.4 Exercices21. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 Arbreet diffusion23 3.1 Diffusion. . . . . . . . . . . . . . 23. . . . . . . . . . . . . . . . . . . . . . . 3.2 Arbrede diffusion. . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . 24 3.3 Innondation24. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Arbrecouvrant. . . . . . . . . . . . 25. . . . . . . . . . . . . . . . . . . . . 3.5 Diffusionavec dtection de la terminaison26. . . . . . . . . . . . . . . . . . 3.6 Concentration. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .27 3

4

TABLE DES MATIèRES

4 LelangageC-distribue29 4.1 Dtectionde la terminaison. . . . . . . . . . . . . . . . . . . . . . . . . .29 4.2 TransformationdeC-distribueenViSiDiA. . . . . . . . . . . . . . . . . . .31 4.3 Ceque ne fait pasViSiDiAet qu’il devrait faire32. . . . . . . . . . . . . . . 4.4 Exercices33. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4.1 Exercice. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .33 4.4.2 Exercice. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .33 4.4.3 Exercice. . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . 33 4.4.4 Exercice: diffusion avec cho. . . . . . . . . . . . . . . . . . . . .34 4.4.5 Exercice. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .34

5 Arbrescouvrants35 5.1 Arbresen largeur d’abord (BFS) [Breath First Search]. . . . . . . . . . . 35. . . . . . . . . . . . . . . . . . . 5.1.1 Dijkstra. . . . . . . . . . . . . . . . . . . .35. . . . . . . . . . . . . 5.1.2 Bellman-Ford. . . . . . . . . . . . . . . . . . .36. . . . . . . . . . . 5.1.3 Rsum36. . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . 5.2 Arbresen profondeur d’abord (DFS) [Depth First Search]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .36 5.3 Arbresde poids minimum (MST) [Minimum Spanning Tree]. . . . . . . . . . . . . . . . . . . . . . . . . . .36 5.3.1 AlgorithmePRIM. . . . . . . . . . 37. . . . . . . . . . . . . . . . . . 5.3.2 AlgorithmeGHS synchrone37. . . . . . . . . . . . . . . . . . . . . . 5.4 Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .37 5.4.1 Exercice. . . . . . . . . . . . . . . . . . . . .37. . . . . . . . . . . .

6 Synchroniseurs39 6.1 Mthodologie39. . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . 6.2 Mesuresde complexit. . . . . . . . . . . . . . . . . .. . . . . . . . . . . 41 6.3 Deuxsynchroniseurs lmentaires43. . . . . . . . . . . . . . . . . . . . . . . 6.3.1 Synchroniseurα. . . . . . . . . . . 43. . . . . . . . . . . . . . . . . . 6.3.2 Synchroniseurβ. . . . . . . . . . . . . . . . . .. . . . . . . . . . . 43 6.4 Synchroniseurγ. . . . . . . . . . . . . . . . . . . . .43. . . . . . . . . . . . 6.5 Compromisoptimal43. . . . . . . . . . . . . . . . . . .. . . . . . . . . . . .

TABLE DES MATIèRES

5

6.6 Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .44

7 Coloration45 7.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .45 7.2 Dfinitiondu problme. . . . . . . . . . . . . . . . . . . . . . . . . . . . .46 7.3 Rductionde palette46. . . . . . . . . . . . . . . . . .. . . . . . . . . . . . 7.4 Colorationdes arbres49. . . . . . . . . . . . . . . . . .. . . . . . . . . . . . 7.4.1 Algorithmepour les 1-orientations. . . . . . . . . . . . . . . . . . .50 7.4.2 LafonctionPosDiff. . . . . . . . . . . . . . . . . . . . . . . . . .51 7.4.3 Analysede l’algorithme. . . . . . . . . . . . . . . . . . . . . . . . .53 7.4.4 Rsum56. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.4.5 Desix  trois couleurs56. . . . . . . . . . . . . . . . . . . . . . . . . 7.5 Colorationdesk-orientations. . . . . . . . . . . . . . . . . . . . . . . . . .58 7.6 Colorationdes cycles, borne infrieure60. . . . . . . . . . . . . . . . . . . . 7.6.1 Colorationdes cycles. . . . . . . . . . . . . . . . . . . . . . . . . .60 7.6.2 Rductionrapide de palette. . . . . . . . . . . . . . . . . . . . . .62 7.6.3 Cyclenon orient. . . . . . . . . . . 63. . . . . . . . . . . . . . . . . 7.6.4 Borneinfrieure64. . . . . . . . . . . . . . . . . .. . . . . . . . . . . 7.7 Exercices72. . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . .

8 Ensemblesindpendants maximaux 8.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2 Algorithmesde base. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3 Rductions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.4 Ensembledominants. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.5 Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

75 75 76 76 77 77

9 Graphescouvrant parses79 9.1 Introduction79. . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 9.2 Calculd’un 3-spanner80. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10 Information quantique85 10.1 Introduction. . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . 85 10.2 Superpositiond’tats. . . . . . . . . . . 86. . . . . . . . . . . . . . . . . . .

6

TABLE DES MATIèRES

10.3 Intrication86. . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 10.4 JeuxCHSH. . . . . . . . . . . . . . . . . . . . .86. . . . . . . . . . . . . . 10.5 JeuxMod4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .86 10.6 Extensiondu modle LOCAL. . . . . . . . . . . . . . . . . . . . . . . . .86 10.7 Lemodle I-LOCAL. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .86 11 Routage et pair-À-pair87 11.1 ...87. . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . 11.2 Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .87 12 Solutions89 13 Travaux pratiques93 14 Projets105

CHAPITRE Introduction 1

Mots cls et notions abordes dans ce chapitre : – systmesdistribus, machines parallles, – passagede messages, mmoire partage, modle PRAM, – synchronisme.

1.1 Qu’estce que le calcul distribuÉ? Une machine (ou architecture)sÉquentiellepermet le traitement d’une seule opra- tion  la fois. Dans un programme squentiel (comme l’extrait ci-dessous) les instructions s’excutent les unes  la suite des autres, dans un ordre bien prcis. 1. x:= x + 1 2. y:= 2*x - 4 3. printy 4. ...

Les machinesparallÈlespermettent le traitement de plusieurs oprations en parallle. En gnrale ces machines permettent d’excuter en parallle de nombreuses instructions lmentaires toutes similaires (SIMD : Single Instruction Multiple Data). Les ordinateurs classiques, les architectures 64 bits ou plus par exemple, sont dj des sortes de machines parallles dans la mesure oÙ elles traitent 64 bits simultanment ( l’intrieur d’un mme cycle machine). Le degr de paralllisme, qui mesure le nombre d’oprations ralisables en parallles, est assez limit dans ce cas. Lorsque le nombre de bits manipuls en parallle devient trs important, on parle de machinesvectorielles(ex : CRAY dans les annes 1990). Sur de telles machines, ont peut par exemple calculerA∙X+BoÙA, Bsont des vecteurs de grandes tailles etXune matrice. Les machines parallles possdent un fort degr de synchronisation.

UnsystÈme distribuÉ(on ne parle plus de machines) est similaire  une machine parallle  la diffrence qu’il y a plusieurs entits de calculs autonomes distantes. Contrairement aux machines parallles, les entits de calcul sont faiblement synchrones (voir compltement

8

CHAPITRE 1.INTRODUCTION

htrognes) et relativement distantes les unes des autres. Typiquement la distance entre les entits autonomes est plus grande d’au moins un ordre de grandeur que les dimensions des entits de calcul. Bien sÛr, tout est une question d’apprciation, car dans une machine squentielle clas- sique on peut trouver des units de calcul parallle (calcul 64 bits, carte GPU) et des processeurs multi-cœurs pouvant tre considrs comme formant un mini-systme distri- bu. Cependant, en gnral tout ou presque tient sur une mme carte mre,  l’intrieur d’une mme machine, d’une mme pice ou d’un mme btiment. Ce n’est pas le cas d’un systme distribu comme Internet. On va voir au paragraphe1.3que la distance est un facteur trs limitant. En rsum, ce qui caractrise les systmes distribus par rapport aux machines paral- lles, c’est :

1. potentiellementbeaucoup plus d’entits de calcul; 2. distancephysique entre entits plus importante.

Le calcul distribu est donc l’art de faire des calculs avec de tels systmes. On fait des calculs avec des systmes distribus pour essentiellement deux raisons :

1. augmenter moindre coup la puissance de calcul et de stockage, en ajoutant graduel- lement des entits, ou en regroupant des ensembles d’entits dj existantes (clusters ou grappes de PC, Grid5000, ...); 2. communiquer entre entits distantes via des protocoles (rseaux LAN, rseaux sa- tellites, Wifi, tlphonie, ...), mais aussi mettre en rapport des banques de donnes rparties (Internet, transactions banquaires, change de fichierspeer-to-peer, ...).

1.2 Uncadre de base pour les systÈmes distribuÉs Les entits de calculs peuvent reprsenter tout un tas d’objets diffrents : des tlphones portables, des tablettes, des processus, des cœurs, des robots, des drÔnes, des oiseaux, des insectes, ... Pour simplifier, on choisira  partir de maintenant le terme de « processeur » comme synonyme d’entit de calcul, bien que ce dernier terme soit plus gnrique. Aussi, on distingue classiquement deux grands modles de systmes distribus selon la manire de communiquer des processeurs.

Passage de messages (message passing).Ce modle traite explicitement des com- munications. Lorsqu’un processeur veut communiquer avec un autre, il doit lui envoyer un message qui transite via un mdium de communications, grce  des instructions du type SendetReceive.

1.2. UNCADRE DE BASE POUR LES SYSTèMES DISTRIBUéS

9

Mmoire partage (shared memory).Au contraire, dans ce modle, les processeurs ne communiquent pas directement. Ils s’changent des informations grce  une mmoire ou des variables communes qu’ils peuvent tous lire et modifier  l’aide d’instructions du typeReadetWrite. Dans ce modle, les instructionsRead/Writeont un coÛt unitaire si bien que le coÛt des communications est pass sous silence. On utilise surtout ce modle pour tudier des problmes lis  l’asynchronisme des lectures/critures, en particulier dans des systmes oÙ des pannes peuvent se produire et ralentir arbitrairement les lectures/critures. Le problme typique tudi est leConcensuset ses nombreuses variantes. Dans sa forme de base les processeurs qui ne sont pas tomb en panne doivent s’accorder sur une valeur, 0 ou 1, initialement propose. Donc, en plus de choisir la mme valeur, les processeurs doivent choisir 0 si tous avaient 0 en entre et tous doivent choisir 1 s’ils avaient 1. Ici, peu importe le nombre ou le coÛt des lectures/critures. Il s’agit de trouver un protocole permettant de rsoudre le problme quelque soit le scenario, chaque processeur excutant le protocole potentiellement  des vitesses diffrentes et variables dans le temps. On parle aussi de protocole sans-attente ouwait-free. En fait, le problme n’a pas de solution en prsence d’une panne de processeur. Une variante a par contre une solution (qu’on ne donnera pas), mme en prsence de pannes :Approximate Agreement. Le problme est similaire  Consensusexcept que si les deux valeurs 0 et 1 ont t initialement proposes, alors les valeurs choisies doivent tre des rels de[0,1], et toutes comprises dans un intervalle de + taille arbitrairement petite [DLP86]. Pour le modle par passage de messages, le coÛt d’une instructionSendest loin d’tre unitaire, surtout si l’metteur et le rcepteur sont distant et n’ont pas de lien direct. C’est donc prcisment l’efficacit des changes de messages qu’on tudie avec ce modle quitte  ngliger le coÛt des calculs locaux des processeurs. Le modle PRAM (pourParallel Random-Access Memory, voir figure1.1) est un cas particulier du modle  mmoire partage. Il est exclusivement synchrone et a pour but l’tude du paralllisme. Il n’est pas questiona prioride processeur en panne. Ce modle se dcline  son tour en de nombreuses variantes suivant la potique adopte pour l’criture simultane dans une mme cellule par plusieurs processeurs. Notons que le modle squentiel RAM est le modle PRAM avecn= 1processeur. Et les lectures/critures se font par dfinition n’importe oÙ en mmoire en temps unitaire. Le modle PRAM est assez loign des systmes distribus rels. En effet, lorsquendevient grand, il n’est plus physiquement possible de garantir la lecture simultane d’une mme cellule mmoire par lesnprocesseurs, et plus gnralement d’avoir un accs en temps uniforme  toutes les ressources par tous les processeurs. On n’en parlera pas dans ce cours, mais ils existent de nombreux travaux qui s’intresse  simuler sur un systme  mmoire partage un algorithme crit pour un systme par passage de messages, ou le contraire. Toute la suite du cours concerne le modle par passage de messages. Dans ce modle il

10

CHAPITRE 1.INTRODUCTION

Figure1.1 – Le modle PRAM : un cas particulier de mmoire partage.

1 existe plusieurs modes de communications.

Point-À-point.Chaque processeur ne peut communiquer directement qu’avec un certain nombre de ses voisins. On modlise de tels systmes naturellement par un graphe connexe (voir la figure1.2). Les sommets sont les processeurs, et les artes les liens directs de communication. On supposera que le graphe est non-orient et sans multi-artes.

Rseau de diffusion (broadcast/radio networks).Chaque processeur peut commu- niquer le mme message simultanment  un certain nombre de rcepteurs, comme un metteur radio le ferait. L encore il y a de nombreuses variantes suivant que les rceptions multiples en un processeur crer ou non de collisions.

1.3 SpÉcificitÉsdu calcul distribuÉ

1.3.1 Lescommunications Elles ne sont pas gratuites! Pour s’en convaincre, considrons un systme oÙ les pro- −9 cesseurs synchrones fonctionnent  une frquence d’horloge de 1 GHz = 10s, soit une cadence de 1 millard de cycles (ou instructions) par seconde. Si les processeurs souhaitent 1. Malheureusement en calcul distribuÉ il existe plusieurs centaines de modÈles cencÈs refletter une rÉalitÉ visiblement difficile À cerner prÉcisÉment.

1.3. SPéCIFICITéSDU CALCUL DISTRIBUé

11

Figure1.2 – Modlisation par graphe du modle point--point. Ici un graphe de Gabriel sur 60 points du plan, oÙ deux pointsxetysont voisins si le disque de diamtre le segment xyne contient aucun autre point.

Figure1.3 – Modlisation d’un rseau de diffusion par un graphe UDG (unit disque graph) gnr  partir d’un nuage de 400 points alatoires non-uniforme pris dans le carr [0,10]×[0,10](figure de gauche). Un point peut communiquer  tous ceux situs dans sa boule de rayon unit (figure de droite). Notez que cet exemple n’est pas un graphe connexe.

faire aussi desSendetReceive cette cadence, alors la distance entre deux processeurs −9 8 P i etP j est au plus10×c, oÙc= 300000km/s =300 000 000m/s =3×10m/s est −9 8 la vitesse de la lumire. Cela fait10×3×010 =.3m = 30 cm.