Vous êtes ici :

Master

Information importante

La page que vous consultez correspond à l'offre de formation 2023-2024.

Trouvez votre formation pour l'année universitaire 2024-2025

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

Enseignement proposé : en présentiel enrichi de ressources pédagogiques numériques

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 d'informatique

7, rue René Descartes
67084 STRASBOURG CEDEX
0368850200

Formulaire de contact


MASTER - Informatique

Partenaires

Logo du CNRS
Logo Établissement associé de l'Université de Strasbourg
Logo du réseau Epicur
Logo de EUCOR, Le Campus européen
Logo de l'Inserm Grand Est
Logo de l'Inria

Labels

Logo du label Bienvenue en France
Logo du programme HRS4R
Logo du programme France 2030
Logo de Service Public+

Réseaux

Logo de France Universités
Logo de la Ligue européenne des universités de recherche (LERU)
Logo du réseau Udice
Logo de l'Université franco-allemande