Algorithmes répartis fondamentaux (ICI 33)
Coordonnateur : François MEUNIER (01 60 76 47 74)

. Connaître les problèmes et algorithmes fondamentaux en algorithmie répartie
. Pouvoir les utiliser dans des applications concurrentes
. Pouvoir aborder ultérieurement des questions plus avancées (synchronizers, réseaux anonymes, tolérance aux pannes)
Remarque : Les algorithmes liés à la gestion de protocole et au routage proprement dit, sont supposés être étudiés par ailleurs

Programme :

Notions de base :
Caractéristiques des réseaux, hypothèses (communication point à point, fiabilité, synchronisme et asynchronisme, topologie...)
Spécification d'un algorithme et évaluation de complexité
Synchronisation par horloges logiques

Plus courts chemins :
A partir d'un centre : algorithmes de Chandly-Misra, Merlin-Segall
Entre toute paire : algorithmes de Toueg (Floyd-Warshall distribué)

Algorithmes par vague et d'exploration :
Principes
Algorithmes de Chang (echo), de Peleg (phases), de Finn
Exploration en profondeur d'abord

Election :
Dans un anneau : algorithmes de Le Lann, Chang-Roberts
Dans un réseau général : algorithmes de Naimi-Trehel, Gallager et al

Détection de terminaison :
Principes
Arbres de calcul : algorihtmes de Dijkstra-Scholten, Shavit-Francez
Aperçu sur notion de snapshot

Organisation pédagogique :

Total cours + contrôle : 21 h
8 vacations de cours de 1 h 30
5 vacations de travaux dirigés de 1 h 30
Contrôle de connaissances : un écrit de 1 h 30

Connaissances requises :
Réseaux (IG1), Systèmes d'exploitation (IG1), Structures de Données (IG1)
Pratique d'un langage de programmation

Documentation ou bibliographie :
"Introduction to distributing algorihtms", G. TEL, Cambridge 1994 (chap. 1,4,6,7,8,10)
"Algorithmique parallèle et distribuée", I. LAVALEE, Hermès 1990