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

Contacts

Responsable(s) de l'enseignement

• Stella Marc-Zwecker
• Anissa Lamani