Articles

ASR

Imprimer

ASR : Introduction à l'algorithmique des applications et des systèmes répartis

Responsable : Michel Raynal (mail)

Équipe pédagogique : Éric Fabre, Michel Raynal (mail)

Description

La plupart des applications et des systèmes sont aujourd'hui formés de sites géographiquement dispersés qui partagent des données ou coopèrent à la réalisation d'un but commun. L'absence de référentiel commun (temps ou mémoire) due à l'environnement réparti crée une problématique particulière qu'il est important de comprendre et de maîtriser. Cela passe par la connaissance de concepts et de techniques appropriées. Le but de ce module est d'en présenter les éléments principaux et, au travers de ceux-ci, d'appréhender la nature et les fondements de ce qu'il est convenu d'appeler le "réparti".

Savoir et savoir faire associés

Savoir: Nature du réparti, temps logique, contrôle réparti
Savoir-faire : Algorithmes répartis, protocoles de contrôle

Structure générale et contenu

  • Nature des applications réparties

    • Notion d'exécution répartie
    • Une exécution est un ordre partiel
    • Concept de causalité
    • État local vs état global
    • Calcul d'un état global cohérent
  • Notion de temps logique
    • Temps linéaire et temps vectoriel
    • Observation d'une exécution répartie
  • Mise en oeuvre de primitives de communication
    • Ordre causal vs ordre total
  • Controle réparti
    • Synchronisation répartie et allocation de ressources
    • Détection de la terminaison et de l'interblocage
    • Aperçu sur la détection des propriétés stables ou instables
  • Cohérence de données réparties
    • Critères de cohérence (atomique vs séquentielle)
    • Protocoles de mise en oeuvre
  • Modèles de concurrence
    • Réseaux d'automates, automates communicants, réseaux de Petri
    • Relations entre ces modèles
    • Sémantiques de trajectoires concurrentes
    • Problèmes classiques sur ces modèles
  • Techniques de dépliage
    • Construction et complexité
    • Utilisation pour la recherche d'accessibilité ou d'interblocages
    • Propriété de factorisation
  • Application à la supervision répartie
    • Primitives de calcul sur les ordres partiels
    • Algorithmique répartie de supervision
    • Ordonnancement des calculs et détection de terminaison

Références bibliographiques

  • Garg V., Elements of distributed computing. Wiley, 2002
  • Raynal M., E Communication and agreement abstractions for fault-tolerant asynchronous distributed systems, Morgan & Claypool, 2010.
  • Attiya and Welch: Distributed Computing, Wiley, 2004

Modalités d'évaluation

Examen écrit de 2 heures mi-décembre

Notes de cours

Buy cheap web hosting service where fatcow web hosting review will give you advices and please read bluehost review for more hosting information.