Description

Cette UE traite des grandes catégories de problèmes théoriques liés à l'algorithmique distribuée, et, dans une moindre mesure, aux systèmes et architectures distribués : définition d'un temps logique, cohérence et diffusion des données réparties, exclusion mutuelle et inter-blocage, état global, etc.
Pour chaque catégorie de problèmes, de nombreuses solutions algorithmiques seront présentées en fonction du contexte (nature des canaux de communication et type d'architecture sous-jacente). Ces solutions, de leur complexité à leur démonstration, seront discutées et comparées en détail. Cette UE sera aussi l'occasion de découvrir et pratiquer un langage de spécification/vérification dédié aux algorithmes distribués, le langage Promela. D'autres aspects plus techniques, tels que MPI ou Erlang, seront également abordés en TP.

Compétences visées

À l'issue de cette UE un étudiant saura :
- Analyser les grandes problématiques liées aux environnements 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 ;
- Choisir entre une architecture centralisée, en anneau, en bus, maillée ou vraiment distribuée en fonction du problème ;
- Manipuler des horloges scalaires, vectorielles et matricielles et ainsi ordonner les événements ;
- Assurer la cohérence d'une diffusion et du partage de l'information en général ;
- Mettre en oeuvre des mécanismes d'exclusion mutuelle appropriés ;
- Résoudre des problèmes d'inter-blocage dans ce contexte ;
- Assurer un ordonnancement efficace sur plusieurs sites ;
- Calculer un état global pour garantir des points de reprise fiables pour le système ;
- S'assurer de la terminaison d'un algorithme réparti ;
- Offrir un service basé sur une élection ;
- Spécifier et vérifier les grands principes algorithmiques d'une solution avec le langage Promela.

Bibliographie

Références :
- 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