CSC 4509 – Algorithmique et communications des applications réparties

Informations générales

Prérequis, objectifs, et mode d'évaluation :

Prérequis

Les étudiants sont invités à vérifier qu'ils possèdent les compétences suivantes :

en algorithmique séquentielle (CSC3101, bonne pratique),
en système d'exploitation UNIX (CSC3102, bonne pratique),
en génie logiciel avec le langage Java (CSC4102, bonne pratique),
en architecture matériel et langage C (CSC4103, bonne pratique),
en programmation réseau avec le langage C (NET4102, connaissance de base),

Objectifs du module

À l'issue du module, les étudiants seront capables, dans le cadre du développement d’une application répartie de petite taille, mais réaliste, et dont le cahier des charges est fourni, de :

développer entièrement une application répartie avec TCP/IP en utilisant la bibliothèque JAVA NIO avec des communications en modes connecté et déconnecté, et en modes synchrone et asynchrone,
lire, donner une exécution, et expliquer les preuves d'algorithmes répartis de base (élection, diffusion, exclusion mutuelle, interblocage et détection de terminaison),
de mettre en œuvre les algorithmes étudiés par insertion dans l'application répartie développée dans le module et avec écriture de scénarios de tests simples (c.-à-d. sans utilisation de canevas logiciel d'émulation ou de simulation) pour vérifier les propriétés de correction et de progression.

À l'issue du module, les étudiants seront aussi capables d'étudier en groupe des articles de recherche sur la thématique de la tolérance aux fautes, d'en discuter avec un spécialiste, et ensuite, d'en faire une présentation synthétique aux autres étudiants de la classe.

Mode d'évaluation

Note =

Partie programmation réseau JAVA NIO : 9 points, dont 2 pour le devoir maison et 7 pour le TP noté
Projet en binôme sur la mise en œuvre d’algorithmes répartis : 8 points
Étude d’un article de recherche en tutorat : 3 points

Tableau de bord

(Légende : date conseillée [sans rendu], date limite [avec rendu])

Thème« programmation d'application répartie
avec JAVA NIO »

Thème« algorithmique répartie »

Thème« mise en œuvre d'algorithmes répartis »

DM Étape 0 (installer le devoir)	06/05
DM Étape 1 (Maven et fichier JAVA NIO)	06/05
DM Étape 2 (TCP avec JAVA NIO)	12/05
DM Étape 3 (Sérialisation, RPC)	22/05
DM Étape 4 (Multithreading)	Optionnelle
Code du DM pour les étapes de 1 à 3 incluse	22/05

QCM Éléments introductifs	S5
QCM Élection	S7
1è lecture et compréhension de l'article	27/05
QCM Diffusion	S10
QCM Exclusion mutuelle	S11
2è lecture et compréhension de l'article	12/06
QCM Interblocage	S12
3è lecture et compréhension de l'article	17/06
QCM Détection de terminaison	S13
Diapositives/QCM de l'article de recherche	≤19/06

Mise en œuvre : installation, ossature de départ	23/05
Mise en œuvre de l'élection	28/05
Mise en œuvre de la diffusion causale	06/06
Mise en œuvre de l'exclusion mutuelle	19/06
Mise en œuvre de la détection de terminaison	25/06
Rapport et code de la mise en œuvre	≤25/06

Séquencement

Sujets

Contenu

Notions clés
Séance 1

Introduction

Introduction au module et à JAVA NIO
- 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é
- 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é
- 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
- 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
Séance 5

Algo. rép., introduction

Algorithmique répartie, introduction
- AVANT : Lecture section 1 « Éléments introductifs »
- Exercices sur les algorithmes de calcul des dépendances causales et de vague Écho (section 1 du polycopié)
- QCM Éléments introductifs (sur Moodle)
- 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
- Utilisation des threads : diapositives version imprimable
- TP sur la communication multiclient et multithread
- Communication multiclient et processus multithreads
Séance 7.1

Algo. rép. élection

Algorithmique répartie, élection
- AVANT : Lecture section 2 « Élection »
- Exercice sur l'algorithme d'élection par vague Écho de Segall
- QCM Élection (sur Moodle)
- 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
- 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)
♦

Rendu DM

Rendu DM
- Date limite : le 22 mai à 23h55
Séance 8

Mise en œuvre

Mise en œuvre des algorithmes répartis
- Mise en œuvre : au besoin, 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
- Mise en œuvre de l'élection
- Scénarios et tests d'intégration avec retardement de transmissions de messages
Réunion 1/3

Réunion LA (1/3)

Réunion étude article (1/3)
- Première réunion avec les tuteurs
Séance 10.1

Algo. rép. diffusion

Algorithmique répartie, diffusion
- AVANT : Lecture section 3 « Diffusion »
- Exercice sur l'algorithme de diffusion causale de Birman et Joseph
- Exercice sur les diffusions FIFO, causale et atomique
- QCM Diffusion (sur Moodle)
- 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
- Selon avancement,
  - mise en œuvre de l'élection
  - mise en œuvre de la diffusion causale
♦

TP noté

TP noté
- Annales
Séance 11.1

Algo. rép. exclusion mutuelle

Algorithmique répartie, exclusion mutuelle
- AVANT : Lecture section 4 « Exclusion mutuelle »
- Exercice sur l'algorithme à base de jeton de Ricart et Agrawala
- QCM Exclusion mutuelle (sur Moodle)
- 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
- Selon avancement,
  - mise en œuvre de la diffusion causale
  - mise en œuvre de l'exclusion mutuelle
Réunion 2/3

Réunion LA (2/3)

Réunion étude article (2/3)
- Deuxième réunion avec les tuteurs
Séance 12

Algo. rép. interblocage

Algorithmique répartie, interblocage
- AVANT : Lecture section 5 « Interblocage »
- 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
- QCM Interblocage (sur Moodle)
- 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 3/3

Réunion LA (3/3)

Réunion étude article (3/3)
- Troisième réunion avec les tuteurs sur la lecture d'article
Séance 13.1

Algo. rép. terminaison

Algorithmique répartie, détection de terminaison
- AVANT : Lecture section 6 « Détection de terminaison »
- Exercice sur l'algorithme de Dijkstra et Scholten
- (En autonomie) Exercice sur l'algorithme de Safra
- QCM Détection de terminaison (sur Moodle)
- 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
Séance 13.2

Mise en œuvre

Mise en œuvre des algorithmes répartis
- Selon avancement,
  - mise en œuvre de l'exclusion mutuelle
  - mise en œuvre de la détection de terminaison
Séance 14.1

Séance 14.1

Exposés — Articles de recherche (1/2)
```
Agenda : à venir
```
Séance 14.2

Mise en œuvre

Mise en œuvre des algorithmes répartis
- 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 (2/2)
```
Agenda : à venir
```
- XXhXX—XXhXX : article 6, Consensus on Transaction Commit.
Séance 15.2

Mise en œuvre

Mise en œuvre des algorithmes répartis
- Selon avancement,
  - mise en œuvre de la détection de terminaison
♦

Rendu final

Rendu final
- Rappel des consignes pour le rendu de la série des TP (code et rapport)
- Date limite : le mardi 25 juin à 23h55