Algorithmes distribués
Master InformatiqueParcours Image et 3D (I3D)
Description
Cette unité d'enseignement présente différents modèles des systèmes distribués et traite des grandes catégories de problèmes théoriques liées à l'algorithmique distribuée. Pour chaque catégorie de problèmes, de nombreuses solutions algorithmiques sont présentées en fonction du contexte (modèle de communication et type d'architecture sous-jacente). Ces solutions, de leur complexité à leur démonstration, sont discutées et comparées en détail. Cette UE permet aussi de découvrir et de pratiquer un langage de spécification/vérification dédié aux algorithmes distribués, le langage Promela. D'autres aspects plus techniques sont également abordés en TP via la plateforme de simulation JBotSim
Compétences requises
À l'entrée de cet enseignement, un étudiant devrait :
- Connaître les problématiques inhérentes aux systèmes centralisés.
- Connaître les principes des architectures réseaux sous-jacentes (modèle OSI et la couche transport en particulier).
- Connaître les principes des algorithmes et des protocoles de communication réseaux.
- Savoir écrire des programmes complexes dans un langage impératif (les séances de TP sont en Promela et en Java).
Compétences visées
À l'issue de cet enseignement un étudiant saura :
- Analyser les grandes problématiques liées aux algorithmes distribués
- Comprendre les limites inhérentes à ce type d'architecture faiblement couplée
- Comparer les solutions algorithmiques distribuées selon des critères variés
- Concevoir et valider un algorithme distribué au moyen d’un langage de spécification de protocoles.
Disciplines
- Informatique
Syllabus
Les algorithmes présentés dans ce cours traitent les problématiques suivantes dans le contexte des systèmes distribués :
- Horloges logiques, ordre total et précédence causale
- Mécanismes de diffusion pour la cohérence et le partage des données réparties
- Exclusion mutuelle.
- Élection d’un leader.
- Détection d’interblocage et de terminaison.
- Calcul d’un état global cohérent pour garantir des points de reprise fiables.
- Consensus.
- Blockchain.
- Protocoles de population.
- Essaim de robots.
- Spécifier et vérifier les grands principes algorithmiques d'une solution distribuée avec le langage Promela.
Bibliographie
- Michel Raynal, Algorithmes distribués et protocoles, Eyrolles, 1984
- Gerard J. Holzmann, Design And Validation Of Computer Protocols, Prentice Hall, 1991
- Michel Raynal, Distributed Algorithms for Message-Passing Systems, Springer, 2013