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 (comme par exemple le langage Promela). Outre la spécification formelle de protocoles, d'autres aspects plus techniques, permettant de simuler voire de mettre en œuvre des algorithmes distribués, seront également abordés en TP.

 

À 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

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

À l'entrée de cette UE, un étudiant devrait :
- avoir connaissance des problématiques inhérentes aux systèmes concurrents (architectures fortement couplées)
- savoir concevoir et manipuler des algorithmes et des protocoles de communication réseaux
- connaître les couches réseaux sous-jacentes (modèle OSI et la couche transport en particulier)
- savoir écrire des programmes complexes dans un langage impératif (les séances de TP sont en Promela et MPI ou Erlang)