UFR de mathématique et d'informatique

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


Cursus master ingénierie (CMI)

Fondation Université de Strasbourg
Investissements d'Avenir
Ligue européenne des universités de recherche (LERU)
EUCOR, Le Campus européen
CNRS
Inserm Grand Est
Logo HRS4R