Algorithmes distribués

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

Contacts

Responsable(s) de l'enseignement