Algorithmique distribuee

Cours : 22.00 h
Travail Individuel : 22.00 h

2.50

module de deuxième année

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.

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
   

IF211

Examen de 2 heures (notes de cours autorisées).

Algoritmique distribuée, arbre, élection, terminaison, pannes, auto-stabilisant