Programme module AD21
Introduction aux algorithmes distribués
Dominante Réseaux
P. Hennequin
Introduire, à partir de quelques exemples les plus classiques, les
notions de base et les problématiques particulières de
l'algorithmique distribué. Ceci se decline en 3 points :
-
Montrer quelques techniques pour prouver
ou analyser des propriétés d'un algorithme distribué,
- Présenter des problèmes inherents aux systèmes
distribués avec les mécanismes classiques permettant de les
aborder.
- Introduire les possibilités ou impossibilités intrinseques
des sytèmes distribués par exemple dans l'approche tolérance
aux fautes.
Après un cours d'introduction (3h), le module s'organise autour de
l'analyse de 4 problèmes d'algorithmique dans les sytèmes
distribués (ou les réseaux) avec une présentation en cours
magistral (1h30) de la problématique et des approches techniques
possibles, et l'analyse en Petite Classe (1h30) d'une solution
algorithmique classique.
Les 4 problèmes envisagés pour ce module sont :
- Algorithme de routage dynamique (Toueg) sur un réseau maillé
et principe de preuve par invariant.
- Réseaux ``anonymes'' et élection probabiliste. Algorithmes d'élection sur un anneau.
- Problème de la terminaison répartie et algorithme de
Dijkstra-Sholten.
- Algorithme de consensus ``crash-robust'' et byzantin,
15 Heures décomposées en :
- 1 séance de 3h de cours Magistral
- 4 séances de 1h30 de cours Magistral et 1h30 de Petite Classe
Le contrôle de connaissance correspond à une petite classe
notée.
Le cours est directement issu de :
Introduction to Distributed Algorithms, Gerard Tel, Cambridge
University Press, 1994.
This document was generated using the LaTeX2HTML translator Version 95 (Thu Jan 19 1995) Copyright © 1993, 1994, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html -split 0 -t Programme Dominante Rezo, Algo Repartis AlgoRep.tex.
The translation was initiated by Pascal Hennequin (LOR-AIGRI) on Wed Jan 15 20:11:23 MET 1997
Pascal Hennequin (LOR-AIGRI)
Wed Jan 15 20:11:23 MET 1997