MASTER INFORMATIQUE : Algorithmique Distribuée 2018

Présentation

Un système distribué est un ensemble d’entités autonomes de calcul (ordinateurs, PDA, processeurs, processus, processus léger, ...) interconnectées et qui peuvent communiquer entre eux. Ce cours est une introduction aux méthodes pour la conception d'algorithmes dans de tels systèmes. Il donne une présentation des différents types de systèmes distribués et des différents problèmes que l'on doit résoudre. Les problèmes abordés sont : l'élection, le consensus, la diffusion, l'exploration, la réplication, et la tolérance aux pannes.

Intervenants : S. Das

Attention : Devoir à la maison (à rendre avant le 3 avril 2018)

Contenu

20 février (LUM) : 21 février (STJ)
Cours 1 : Introduction et Problèmes fondamentaux [slides]
  • Modèles Différents
  • Complexité de la communication
  • Problème de l'Election dans l'anneau (impossibilité, LCR, Phases) [Santoro] 3.3
  • Algorithme d'inondation
  • Problème de consensus, impossibilité [Tel] 14.1
TD 1 : Algorithmes pour les problèmes fondamentaux [Fichier]
TP 1: Simulation d'algorithmes d'Election avec DAVIS
27 février : 28 février
(Vacances Scolaires)
06 mars (LUM) : 07 mars (STJ)
Cours 2 : Algorithmes pour les réseaux asynchrones [slides]
  • Calcul sur les arbres, Construction d'arbre couvrant : [Santoro] 2.5,2.6
  • Election sur graphe quelconque, bourne inférieur, algorithme GHS, Yo-Yo, KKM : [Santoro] chapitre 3, [Tel] 7.3, 7.4
  • Election sur la classe de graphes spécifiques [Santoro] 3.4, 3.5, 3.6, 3.7
  • Synchronisers [Tel] 12.3
Fichiers:
TD 2 : Algorithmes pour les Réseaux Asynchrones [Fichier]
TP 2: Algorithmes pour l'Election dans les anneaux bidirectionnels
13 mars (LUM) : 14 mars (STJ)
Cours 3: Les réseaux synchrones [slides]
  • Calculs Synchrones et Synchronisation, horloge logique : [Santoro] 6.2, 6.3, 6.4, [Tel] 2.3
  • Detection de Propriétés Globales, Deadlock & Terminaison : [Santoro] 8.2, [Tel] 8.1, 8.2, 8.4
  • Tolerance aux Pannes (Fautes permanents) [Santoro] 7.1, 7.3.1-7.3.3
TD 3 : Algorithmes pour les Réseaux Synchrones [Fichier]
TP 3: Algorithmes pour la construction d'Arbre Couvrant
20 mars (LUM) : 21 mars (STJ)
Cours 4: Tolerance aux pannes [slides]
  • Tolerance aux Pannes (Reseaux Asynchrones), Fautes Dynamiques : [Tel] 14.1, 14.2, [Santoro] 7.8
  • Failure Detector, Stabilization : [Tel] 16.1, 16.2, 17.1, 17.2.1, 17.2.3
  • Algorithmes Randomisés pour Election et Consensus [Santoro] 6.3.1, 7.4.2
  • Données Distribués, Algorithmes Distribués de Tri [Santoro] 5.2, 5.3
TD 4 : Algorithmes Randomisé & Données Distribués [Fichier]
TP 4: Election et Réseaux Anonymes
27 mars (LUM) : 28 mars (STJ)
Cours 5: Agents Mobiles [slides]
  • Modèle d'agent mobiles, motivation, et les problèmes fondamentaux
  • Exploration d'un graphe par agent mobile
  • Rendez-vous de deux agents dans anneau, arbre, ou graphe connu
  • Rendez-vous dans les graphes inconnu avec tableau blanc
  • Décontamination / Capture d'intrus dans un réseau
  • Tolérance aux Pannes : Recherche de Trou Noir dans un réseau
TD 5: Algorithmes pour les agents mobiles
TP 4: Simulation d'algorithmes pour les agents mobiles

Evaluation : Note Finale = MAX { Examen, (2*Examen + DM)/3 }

DM = Devoir à la maison : Travail Individuel, à faire à la maison et à rendre par courriel
Date de diffusion : 26 mars 2018
Date Limité de soumission : 3 avril 2018 (Les devoirs reçues après cette date ne seront pas acceptées).
Vous pouvez m'envoyer votre travail (format 'PDF' ou 'txt') par courriel à : shantanu.das @ lif.univ-mrs.fr

Examen Final:
Le 3 avril 2018: 15h - 17h
Les documents ne sont pas autorisés.

Bibliographie

[Santoro] :
Distributed Algorithms : Design and Analysis, Nicola Santoro, Wiley 2007.
[Tel] :
Introduction to Distributed Algorithms, Gerard Tel, 2eme Edition, Cambridge University Press, 2000.

Autres Littérature :