Année 2006-2007
Master-2 Recherche Informatique : Systèmes et Logiciel
Algorithmique et techniques de base des systèmes
répartis
S. Krakowiak
Cours de 24 heures, 1er trimestre
Recommandé pour le Profil : Systèmes et Applications
Parallèles et Répartis, Réseaux et
Multimédia
Version anglaise
La conception et la réalisation des systèmes et
applications répartis s'appuient sur un ensemble de principes de
base régissant la communication, la gestion de l'information, le
partage de ressources, la tolérance aux fautes. L'objectif de ce
module est de présenter ces principes en les illustrant par des
exemples concrets d'application. Les aspects suivants sont
examinés.
- Temps et état dans un système réparti.
Application : datation, observation, mise au point, synchronisation.
- Algorithmes de base des systèmes répartis
(élection, terminaison, etc). Applications : gestion de groupes,
calcul réparti.
- Tolérance aux fautes, diffusion fiable, gestion de
groupes. Applications : serveurs fiables, gestion de copies multiples.
- Consensus et validation. Applications : service de consensus,
transactions réparties.
- Gestion répartie de l'information. Applications :
cohérence de caches, objets répartis
L'accent est mis sur les principes de base. Pour chaque classe de
méthodes, on indique schématiquement son utilisation dans
la conception de systèmes réels.
Temps et état dans un système réparti.
- Causalité et ordonnancement des événements
dans un système réparti
- État global d'un système réparti ; coupures
cohérentes
applications : algorithmes de sauvegarde-reprise, détection de
propriétés stables - Ordonnancement global par horloges
logiques
applications : exclusion mutuelle, files d'attente réparties -
Ordonnancement causal par horloges vectorielles
applications : observation, mise au point - Synchronisation
d'horloges physiques
Coopération de processus répartis
- Anneau virtuel, protocoles d'insertion, retrait, gestion des
défaillances.
- Algorithmes d'élection
application : gestion de groupes - Algorithmes de détection
de terminaison
application : ramasse-miettes réparti
Tolérance aux fautes
- Hypothèses de pannes
- Spécification de la cohérence :
linéarisabilité, cohérence séquentielle,
cohérence causale
- Copie primaire et duplication active
- Algorithmes de diffusion fiable et gestion de groupes de processus
- diffusion fiable, causale, atomique
- gestion de groupes, vues synchrones
- Applications : serveurs fiables, gestion de copies multiples
Consensus et validation
- Classes de détecteurs de défaillances
- Problème du consensus
Quelques cas particuliers (omission synchrone, byzantin synchrone ou
non) - Protocoles de décision : validation à 2 ou 3
phases
applications : gestion répartie de transactions
Gestion répartie de l'information
- Principes de la gestion d'objets répartis
- Mise en oeuvre : mémoire virtuelle, objets répartis
- Diffusion à grande échelle
- Gestion de caches, duplication, cohérence
- Applications : systèmes P2P
Bibliographie
Ouvrages de référence
- R. Guerraoui, L. Rodrigues, Reliable Distributed Programming, Springer, 2006
- A. S. Tanenbaum, M. van Steen, Distributed
Systems - Principles & Paradigms, Prentice Hall, 2002
- S. Mullender (editor), Distributed Systems, 2nd ed. ,
Addison-Wesley, 1993
- M. Singhal, N. G. Shivaratri, Advanced Concepts in Operating
Systems, McGraw-Hill, 1994
- V. C. Barbosa, Introduction to Distributed Algorithms,
MIT Press, 1996