Algorithmes distribués
Master InformatiqueParcours Image et 3D (I3D)
ComposanteUFR de mathématique et d'informatique
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