Syllabus 2014/2015
 
Extrait PDF Anglais
Français
index
Module : IF208
Titre :
Algorithmique distribuee
Volumes horaires :
Cours : 22.00 h
Travail Individuel : 22.00 h
Crédits ECTS :
2.50
Niveau :
module de deuxième année
Résumé :
Ce cours est une introduction à l'algorithmique distribuée. Il commence par une présentation des systèmes distribués et des différents problèmes que l'on doit résoudre suivant le type de système: grands réseaux, réseaux locaux, machines multi-processeurs ou bien machine unique abritant plusieurs processus. Les calculs locaux et en particulier les réécritures de graphes constituent le principal formalisme utilisé pour exprimer les problèmes, leurs solutions et les preuves. Pour chaque problème, on montrera l'importance des hypothèses faites sur le réseau ou de la connaissance que l'on a du réseau. On étudiera le passage de la frontière entre ce que l'on peut faire et ce que l'on ne peut pas faire. On montrera également comment des problèmes n'admettant pas de solution déterministe peuvent être très facilement et très effiocacement résolus par des algorithmes probabilistes.
Plan :
  1. Introduction - Présentation de différents modèles
  2. Calcul d'un arbre couvrant
  3. Election
  4. La reconnaissance
  5. Détection de la terminaison
  6. Algorithmes distribués probabilistes
  7. Algorithmes auto-stabilisants
  8. Détection et tolérance aux pannes
Prérequis :
IF211
Mot(s) clé(s) :
Algoritmique distribuée, arbre, élection, terminaison, pannes, auto-stabilisant