Systèmes répartis

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 du 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 et pour prouver les algorithmes distribués vus en cours. Les différents problèmes abordés sont : le calcul d'un arbre recouvrant, le problème de la reconnaissance, l'élection, la détection de la terminaison et plus généralement la détection de propriétés stables, calcul d'un état global, algorithmes distribués probabilistes, résistance aux pannes : algorithmes auto-stabilisants. Pour chacun de ces problèmes, 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 où passe 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 efficacement résolus par des algorithmes probabilistes.

1. Introduction , Présentation générale des différents modèles
2. Calcul d'un arbre recouvrant
3. Election
4. La reconnaissance
5. Détection de la terminaison
6. Algorithmes probabilistes
7. Algorithmes auto-stabilisants
8. Détection et tolérance aux pannes

C. Lavault Evaluation des algorithmes distribués 1995 Hermes /

G. Tel Introduction to distributed algorithms 2000 Cambridge University Press