 | editer cette page |
Introduction à l'algorithmique des applications et des systèmes répartis (ASR)
Responsable :
Michel Raynal
Équipe pédagogique : Éric Fabre, Achour Mostéfaoui, Michel Raynal
Description
La plupart des applications et des systèmes sont aujourd'hui formés de sites géographiquement dispersés qui partagent des données ou coopèrent à la réalisation d'un but commun. L'absence de référentiel commun (temps ou mémoire) due à l'environnement réparti crée une problématique particulière qu'il est important de comprendre et de maîtriser. Cela passe par la connaissance de concepts et de techniques appropriées. Le but de ce module est d'en présenter les éléments principaux et, au travers de ceux-ci, d'appréhender la nature et les fondements de ce qu'il est convenu d'appeler le "réparti".
Structure générale et contenu
- Nature des applications réparties
- Notion d'exécution répartie
- Une exécution est un ordre partiel
- Concept de causalité
- État local vs état global
- Calcul d'un état global cohérent
- Notion de temps logique
- Temps linéaire et temps vectoriel
- Observation d'une exécution répartie
- Mise en oeuvre de primitives de communication
- Ordre causal vs ordre total
- Controle réparti
- Synchronisation répartie et allocation de ressources
- Détection de la terminaison et de l'interblocage
- Aperçu sur la détection des propriétés stables ou instables
- Cohérence de données réparties
- Critères de cohérence (atomique vs séquentielle)
- Protocoles de mise en oeuvre
- Modèles de concurrence
- Réseaux d'automates, automates communicants, réseaux de Petri
- Relations entre ces modèles
- Sémantiques de trajectoires concurrentes
- Problèmes classiques sur ces modèles
- Techniques de dépliage
- Construction et complexité
- Utilisation pour la recherche d'accessibilité ou d'interblocages
- Propriété de factorisation
- Application à la supervision répartie
- Primitives de calcul sur les ordres partiels
- Algorithmique répartie de supervision
- Ordonnancement des calculs et détection de terminaison
- Lamport L. Time, clocks and the ordering of events in a distributed systems. Comm. ACM, 21(7):558-565,1978
- Garg V. Elements of distributed computing. Wiley, 2002
Documents de cours
- Partie M. Raynal
- Partie É. Fabre
- Partie A. Mostefaoui