CSC 4509 – Algorithmique et communications des applications réparties

Informations générales

Tableau de bord

Séquencement

• Sujets
  Contenu
  
  Notions clés
• Séance 1
  Introduction
  Introduction au module et à JAVA NIO
  Mardi 7 mai
  Denis Conan puis Éric Lallet
  • Présentation du module : diapositives
  • Introduction à JAVA NIO : diapositives (version imprimable)
  • Manipulation de fichiers avec JAVA NIO : TP Manipulation de fichiers
  • Installer le devoir maison
  • Commencer la première étape du devoir maison
  • Buffers et channels de JAVA NIO
  • (optionnel) Buffer de type direct
  • (optionnel) Mapping de fichier en mémoire
• HP
  avant séance 2
  Travail hors présentiel avant la Séance 2
  
  • Lire les pages 1 à 13 de la documentation sur JAVA NIO (≈ 30 mn)
  • Terminer la première étape du devoir maison
  • (optionnel) les usages des buffers optimisés : TP Utilisation avancée des ByteBuffer
  • Lire les tutoriels sur les interfaces avec des constantes, le static import, les énumérations (≈ 20 mn)
• Séance 2
  JAVA NIO, comm. mode déconnecté
  JAVA NIO, communication en mode déconnecté
  Mardi 14 mai
  Éric Lallet
  • Adressage TCP—UDP/IP et communication avec JAVA NIO : diapositives (version imprimable)
  • Présentation de la bibliothèque Log4j : diapositives (version imprimable)
  • Communication en mode « échange de messages » (datagram) : TP communication en mode datagram
  • Première partie des communications en mode connecté : TP flot de données versus datagram
  • Communication en mode datagram (service d'UDP)
  • Classe DatagramChannel de JAVA NIO
• HP
  avant séance 3
  Travail hors présentiel avant la séance 3
  
  • Commencer la deuxième étape du devoir maison
  • Terminer le TP
  • Lire le tutoriel sur la sérialisation des objets JAVA (≈ 45 mn)
• Séance 3
  JAVA NIO, comm. mode connecté
  JAVA NIO, communication mode connecté
  Mercredi 15 mai
  Éric Lallet
  • Envoi d'information avec TCP : diapositives (version imprimable)
  • Interface fonctionelle et expression lambda : diapositives (version imprimable)
  • Seconde partie des communications en mode connecté : TP échange d'objets sérialisés en mode connecté
  • Communication en mode connecté (service de TCP)
  • Classes SocketChannel et ServerSocketChannel de JAVA NIO
  • Transmission d'objets sérialisés
• HP
  avant séance 4
  Travail hors présentiel avant la séance 4
  
  • Commencez la troisième étape du devoir maison (à terminer avant le 27 mai)
  • Lire les pages 19 à 23 de la documentation sur JAVA NIO (≈ 30 mn)
• Séance 4
  JAVA NIO, asynchronisme
  JAVA NIO, sélecteurs, asynchronisme
  Vendredi 17 mai
  Éric Lallet
  • Communications asynchrones avec JAVA NIO : diapositives ( version imprimable)
  • Classe Selector de JAVA NIO
  • TP sur la communication en mode asynchrone
  • Communications asynchrones avec la classe Selector de JAVA NIO
• HP
  avant séance 5
  Travail hors présentiel avant la séance 5
  
  • Lecture de la section « introduction » du cours (section 1 du polycopié)
• Séance 5
  Algo. rép., introduction
  Algorithmique répartie, introduction
  Mardi 21 mai
  Denis Conan
  • Exercices sur les algorithmes de calcul des dépendances causales et de vague Écho (section 1 du polycopié)
  • Modèle de système réparti, machine à états, synchrone versus asynchrone, type de défaillance
  • Convention d'écriture des algorithmes répartis
  • Ordre causal, horloge (scalaire, vectorielle, matricielle)
  • Algorithmes de calcul des dépendances causales
  • Algorithmes de vague et de traversée de graphe
• HP
  avant séance 6
  Travail hors présentiel avant la séance 6
  
  • Lire le tutoriel sur les threads jusqu'à la page « Intrinsic Locks and Synchronization » (≈ 1 h)
• Séance 6
  JAVA NIO, asynchronisme
  JAVA NIO, asynchronisme (suite), multiclient, multithreading
  Mercredi 22 mai
  Éric Lallet
  • Utilisation des threads : diapositives version imprimable
  • TP sur la communication multiclient et multithread
  • Communication multiclient et processus multithreads
• HP
  avant séance 7
  Travail hors présentiel avant la séance 7
  
  • Faire le QCM introduction (sur Moodle) avant la séance 7
  • Lecture de la section « élection » du cours (section 2 du polycopié)
• Séance 7.1
  Algo. rép. élection
  Algorithmique répartie, élection
  Mardi 28 mai
  Denis Conan
  • Exercice sur l'algorithme d'élection par vague Écho de Segall
  • Spécification de l'élection
  • Élection dans un anneau
  • Élection dans une topologie quelconque
• Séance 7.2
  Mise en œuvre
  Mise en œuvre des algorithmes réparties
  Mardi 28 mai
  Denis Conan
  • Mise en œuvre — installations, création du projet
  • Mise en œuvre — étude de l'ossature de départ de l'application
  • Types paramétrés, inférence de type (diamond), type Joker
  • Classes anonymes, interfaces avec attributs
  • Idiomes: objets et collections non modifiables/immuables, intercepteur (p.ex. via default method d'interface)
  • Import static, bloc de code static
  • Types énumérés, constructeur, ordinal(), values()
  • Synchronisation, synchronized(ref)
• HP
  Rendu DM
  Rendu DM
  
  • Rendu du devoir maison JAVA NIO avant le 27 mai à 23h55
• HP
  Avant séance 8
  Travail hors présentiel avant la séance 8
  • Faire le QCM élection (sur Moodle) avant la séance 8
  • Terminer l'étude de l'ossature de départ de l'application répartie
• Séance 8
  Mise en œuvre
  Mise en œuvre des algorithmes répartis
  Mercredi 29 mai
  Denis Conan et Éric Lallet
  • Mise en œuvre : si ce n'est le cas, terminer l'étude de l'ossature de départ de l'application répartie
  • Mise en œuvre de l'élection
  • Scénarios et tests d'intégration avec retardement de transmissions de messages
• Séance 9
  Mise en œuvre
  Mise en œuvre des algorithmes répartis
  Jeudi 30 mai
  Denis Conan et Éric Lallet
  • Mise en œuvre de l'élection
  • Scénarios et tests d'intégration avec retardement de transmissions de messages
• HP
  avant séance 10
  Travail hors présentiel avant la séance 10
  
  • Lecture de la section « diffusion » du cours (section 3 du polycopié)
  • Mise en œuvre de l'élection
• TP noté
  TP noté
  TP noté
  Vendredi 31 mai
  Denis Conan et Éric Lallet
  • TP noté sur la partie programmation réseau
• Séance 10.1
  Algo. rép. diffusion
  Algorithmique répartie, diffusion
  Lundi 3 juin
  Denis Conan
  • Exercice sur l'algorithme de diffusion causale de Birman et Joseph
  • Exercice sur les diffusions FIFO, causale et atomique
  • Spécifications des diffusions fiables, FIFO, causale et totale (atomique)
  • Algorithme de diffusion causale à base d'horloges vectorielles
• Séance 10.2
  Mise en œuvre
  Mise en œuvre des algorithmes répartis
  Lundi 3 juin
  Denis Conan
  • Selon avancement,
    • mise en œuvre de l'élection
    • mise en œuvre de la diffusion causale
• HP
  avant séance 11
  Travail hors présentiel avant la séance 11
  • Faire le QCM diffusion (sur Moodle) avant la séance 11
  • Lecture de la section « exclusion mutuelle » du cours (section 4 du polycopié)
  • Travail sur la mise en œuvre de la diffusion
• Séance 11.1
  Algo. rép. exclusion mutuelle
  Algorithmique répartie, exclusion mutuelle
  Mercredi 5 juin
  Denis Conan
  • Exercice sur l'algorithme à base de jeton de Ricart et Agrawala
  • Spécification de l'exclusion mutuelle
  • Algorithmes à base de permissions, structure informationnelle générique
  • Algorithmes à base de jeton
• Séance 11.2
  Mise en œuvre
  Mise en œuvre des algorithmes répartis
  Mercredi 5 juin
  Denis Conan
  • Selon avancement,
    • mise en œuvre de la diffusion causale
    • mise en œuvre de l'exclusion mutuelle
• Réunion 1/3
  Réunion LA (1/3)
  Réunion Lecture Articles (1/3)
  Vendredi 7 juin
  • Première réunion avec les tuteurs
• HP
  avant séance 12
  Travail hors présentiel avant la séance 12
  
  • Faire le QCM exclusion mutuelle (sur Moodle) avant la séance 12
  • Lecture de la section « interblocage » du cours (section 5 du polycopié)
  • Selon avancement, travail sur la mise en œuvre de la diffusion causale et de l'exclusion mutuelle
• Séance 12
  Algo. rép. interblocage
  Algorithmique répartie, interblocage
  Lundi 10 juin
  Denis Conan
  • Exercice sur la prévention de l'interblocage dans le modèle ET
  • Exercice sur la construction de coupures cohérentes pour la détection d'interblocage
  • Modèles d'interblocage ET, OU—ET
  • Condition de déblocage, définition de l'interblocage
  • Stratégie contre l'interblocage (prévention, évitement, et détection puis résolution)
  • Prévention dans le modèle ET avec les algorithmes de Rosenkrantz, Stearns et Lewis
  • Détection d'interblocage à base de construction de coupures cohérentes, algorithme de Chandy et Lamport
• Réunion 2/3
  Réunion LA (2/3)
  Réunion Lecture Articles (2/3)
  Jeudi 13 juin
  • Deuxième réunion avec les tuteurs
• HP
  avant séance 13
  Travail hors présentiel avant la séance 13
  
  • Faire le QCM interblocage (sur Moodle) avant la séance 13
  • Lecture de la section « détection de terminaison » du cours (section 6 du polycopié)
  • Travail sur la mise en œuvre de l'exclusion mutuelle
  • Rendu des diapositives de présentation des études des articles de recherche au plus tard la veille de la présentation
• Séances 13.1
  Séance 13.1
  Exposés — Articles de recherche (1/3)
  Lundi 17 juin après-midi
  Denis Conan

  Agenda :
  - 14h30—15h15 : article 2, The Failure Detector Abstraction,
  - 15h15—16h00 : article 6, Consensus on Transaction Commit.
• Séance 13.2
  Algo. rép. terminaison
  Algorithmique répartie, détection de terminaison
  Lundi 17 juin aprés-midi
  Denis Conan
  • Exercice sur l'algorithme de Dijkstra et Scholten
  • Spécification de la détection de terminaison, modèle d'interblocage OU, configuration terminale et finale, états actif et passif, algorithme de contrôle
  • Détection de terminaison par construction de coupure cohérente
  • Détection de terminaison par calcul du graphe d'exécution, algorithme de Dijkstra et Scholten pour un arbre d'exécution, de Shavit et Francez pour un graphe quelconque d'exécution, de Safra dans une topologie des processus en anneau
• HP
  après séance 13
  Travail hors présentiel après la séance 13
  
  • Faire le QCM détection de terminaison (sur Moodle) après la séance 13
  • Travail sur les mises en œuvre
• Réunion 3/3
  Réunion LA (3/3)
  Réunion Lecture Articles (3/3)
  Mardi 18 juin
  • Troisième réunion avec les tuteurs
• Séance 14.1
  Séance 14.1
  Exposés — Articles de recherche (2/3)
  Jeudi 20 juin matin
  Denis Conan

  Agenda :
  - 10h00—10h45 : article 1, Fundamentals of Fault-Tolerant Distributed Computing in Asynchronous Environments,
  - 10h45—11h30 : article 3, A Survey of Rollback-Recovery Protocols in Message-Passing Systems.
          
• Séance 14.2
  Mise en œuvre
  Mise en œuvre des algorithmes répartis
  Jeudi 20 juin matin
  Denis Conan
  • Selon avancement,
    • mise en œuvre de l'exclusion mutuelle
    • mise en œuvre de la détection de terminaison
• Séance 15.1
  Séance 15.1
  Exposés — Articles de recherche (3/3)
  Vendredi 21 juin matin
  Denis Conan

  Agenda :
  - 10h00—10h45 : article 5, Total Order Broadcast and Multicast Algorithms: Taxonomy and Survey,
  - 10h45—11h30 : article 4, Group Communication Specifications: A Comprehensive Study.
• Séance 15.2
  Mise en œuvre
  Mise en œuvre des algorithmes répartis
  Vendredi 21 juin
  Denis Conan
  • Selon avancement,
    • mise en œuvre de la détection de terminaison
• HP
  Rendu final
  Rendu final
  Mardi 25 juin
  
  • Rappel des consignes pour le rendu de la série des TP (code et rapport)
  • Déposer dans le dépôt Git de GitLab la mise en œuvre de la détection de terminaison avant le mardi 25 juin à 23h55