Algorithmes distribués

  • Cours (CM) 24h
  • Cours intégrés (CI) -
  • Travaux dirigés (TD) 24h
  • Travaux pratiques (TP) 12h
  • Travail étudiant (TE) -

Langue de l'enseignement : Français

Niveau de l'enseignement : B2-Avancé - Utilisateur indépendant

Description du contenu de l'enseignement

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 à acquérir

À 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, lectures recommandées

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

Pré-requis recommandés

À 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)

Contact

UFR de Mathématique et Informatique

7 RUE RENE DESCARTES
67084 STRASBOURG
0368850123

Formulaire de contact


MASTER - Informatique