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