Languages and algorithms for distributed Applications

Enseignants

Riviere Etienne;

Langue
d'enseignement

Anglais
> Facilités pour suivre le cours en français

Préalables

Thèmes abordés

• Etude des bases théoriques des algorithmes répartis, et des langages pour la programmation répartie.
• Etude des questions spécifiques des systèmes répartis et mobiles: répartition géographique, gestion de ressources localisées et réparties, tolérance aux fautes, sécurité, interopérabilité et ouverture.
• Utilisation pratique de quelques langages représentatifs et avancés pour la programmation de systèmes collaboratifs, répartis et mobiles.

Acquis
d'apprentissage

A la fin de cette unité d’enseignement, l’étudiant est capable de :

Eu égard au référentiel AA du programme « Master ingénieur civil en informatique », ce cours contribue au développement, à l'acquisition et à l'évaluation des acquis d'apprentissage suivants : INFO1.1-3 INFO2.2-4 INFO5.4-5 INFO6.1, INFO6.5 Eu égard au référentiel AA du programme « Master [120] en sciences informatiques », ce cours contribue au développement, à l'acquisition et à l'évaluation des acquis d'apprentissage suivants : SINF1.M2 SINF2.2-4 SINF5.4-5 SINF6.1, SINF6.5 Les étudiants ayant suivi avec fruit ce cours seront capables de: définir les systèmes répartis et les algorithmes répartis avec les concepts qu'ils contiennent et les propriétés qu'ils donnent aux programmes; concevoir des applications collaboratives sur des systèmes répartis en utilisant des modèles rigoureux qui permettent de gérer la concurrence et les pannes partielles; implémenter des applications collaboratives sur des systèmes répartis en utilisant les techniques appropriées; utiliser un certain nombre d'outils avancés pour le développement d'applications réparties et mobiles. Les étudiants auront développé des compétences méthodologiques et opérationnelles. En particulier, ils ont développé leur capacité à: penser à l'aide d'abstractions (raisonner correctement sur un système qui comprend plusieurs couches d'abstractions, et de définir de nouvelles abstractions pour simplifier la résolution d'un problème).

Contenu

Le cours est organisé en deux parties.
Dans la première partie, nous abordons les résultats et algorithmes classiques des systèmes distribués à passage de messages, où les nœuds se connaissent et peuvent communiquer entre eux dans un cadre de taille relativement restreinte. Cette partie comprend :

• Introduction aux systèmes distribués
• Programmation distribuée à l’aide du langage à acteurs Elixir
• Modèles formels et spécifications des systèmes distribués (sûreté et vivacité)
• Algorithmes de graphes distribués
• Le temps et ordonnancement des événements
• Algorithmes de diffusion
• Coordination : exclusion mutuelle, élection de leader
• Algorithmes de consensus et détecteurs de pannes
• Réplication de machine à états
• Tolérance aux pannes arbitraires (byzantines)

Dans la seconde partie, nous nous concentrons sur les systèmes distribués opérant à l’échelle d’Internet et dans des conditions adverses. Cette seconde partie couvre :

• Diffusion et coordination par algorithmes épidémiques (gossip)
• Réseaux logiques structurés (par ex., tables de hachage distribuées)
• Systèmes de blockchain (par ex., Bitcoin, Ethereum, Hyperledger Fabric)
• Systèmes de stockage de données décentralisés (par ex., IPFS)
• Sujets choisis en fonction des avancées récentes du domaine et des recherches du professeur (exemples non exhaustifs : systèmes de publication/abonnement, réseaux de blockchain de couche 2, systèmes mobiles ad hoc, systèmes local-first et CRDT, …)

Méthodes d'enseignement

• Cours magistral hebdomadaire avec le professeur ;
• Séances d’exercices hebdomadaires avec les assistants, comprenant la résolution de problèmes sur papier et des exercices de programmation en Elixir (dans la partie 1) ;
• Séances guidées et tutoriels hebdomadaires liés au projet de programmation (dans la partie 2).

Modes d'évaluation
des acquis des étudiants

L’évaluation pour la session de janvier est la suivante :

• Examen de mi-parcours : 0 % ou 25 %, voir ci-dessous (vers la semaine 8, sur le contenu de la partie 1 uniquement)
• Projet : 25 %, basé sur un livrable logiciel documenté et une défense orale
• Examen final : 50 % si la prise en compte de l’examen de mi-parcours à hauteur de 25 % est avantageuse pour l’étudiant, et 75 % sinon (pendant la session, sur le contenu des parties 1 et 2)

Le projet est obligatoire et se déroule pendant le quadrimestre. Il ne peut être réalisé qu’une seule fois et compte pour l’ensemble de l’année académique. L’examen de mi-parcours est également obligatoire et ne peut être repassé lors de la session de septembre.
L’évaluation pour la session de septembre est la suivante :

• Examen de mi-parcours : 0 % ou 25 %, voir ci-dessous (conservé depuis la session de janvier)
• Projet : 25 % (conservé depuis la session de janvier)
• Examen final : 50 % si la prise en compte de l’examen de mi-parcours à hauteur de 25 % est avantageuse pour l’étudiant, et 75 % sinon (sur le contenu des parties 1 et 2)

L’ensemble du matériel de cours est fourni en anglais. Les étudiants peuvent répondre aux questions d’examen et présenter leur projet en anglais ou en français.
Les examens de mi-parcours et final peuvent utiliser tout ou partie des modalités d’évaluation suivantes. La proportion respective de points pour chaque partie est annoncée en début d’examen :

• Questions ouvertes sur le contenu du cours
• Problèmes ouverts nécessitant l’application des compétences et connaissances acquises pendant le cours
• Questions à choix multiples et à réponses multiples selon le principe du « standard-setting ». Une réponse incorrecte à l’une des questions ne peut entraîner de note négative, et cette partie de l’examen ne peut, dans son ensemble, accorder de points négatifs. Toutefois, un seuil minimal (annoncé lors de l’examen) de réponses correctes est nécessaire pour obtenir effectivement des points pour cette partie de l’examen.

Le professeur peut demander à un étudiant de passer un examen oral supplémentaire, en plus de l’examen de mi-parcours ou final et/ou du projet, notamment (mais pas exclusivement) en cas de problèmes techniques ou de suspicion d’irrégularités.
Règles relatives à l’utilisation de l’intelligence artificielle (IA) pour le projet
L’utilisation responsable de l’IA pour l’implémentation du projet en langage Elixir est acceptée sous les règles suivantes:

• Les étudiants doivent assumer la pleine responsabilité de leur travail et être capables d’expliquer oralement l’ensemble du code et des livrables (documentation, scripts de déploiement, etc.) remis dans le cadre du projet.
• L’utilisation de l’IA doit être précisément documentée dans la documentation du projet, dans une section dédiée indiquant quelles IA ont été utilisées et pour quelle partie. La soumission de code ou de documentation généré partiellement ou entièrement par une IA sans documenter cette utilisation sera considérée comme du plagiat. Les étudiants qui n’ont pas utilisé d’IA doivent également l’indiquer dans cette section. L’absence de déclaration relative à l’IA dans le projet entraînera une pénalité de -5/20 points.
• Une utilisation jugée abusive de l’IA, compromettant l’acquisition des connaissances visées par le projet, peut être considérée comme une irrégularité au sens de la Section 7, Articles 107 et suivants du Règlement général des études et des examens (RGEE), avec toutes les conséquences que cela implique, comme prévu aux Articles 111 et suivants. En cas de suspicion d’utilisation abusive de l’IA dans le projet remis, ou de déclaration d’utilisation de l’IA incomplète ou inexacte, l’enseignant du cours peut convoquer l’étudiant concerné pour un entretien oral supplémentaire et prendre les mesures nécessaires en concertation avec le président du jury de l’EPL.

Autres infos

Connaissance de la programmation de base. Une expérience en programmation concurrente et/ou en langages fonctionnels (comme abordé, par exemple, dans LINFO1131) est un atout, mais pas une exigence stricte.
LINFO2345 est conçu pour être complémentaire aux cours suivants :

• LINFO2145 (Cloud computing) traite des applications distribuées pour le cloud ainsi que de la gestion et du traitement des données associées, à un niveau plus élevé et avec un accent plus marqué sur les aspects de génie logiciel et de systèmes d’exploitation. Il bénéficie néanmoins de la compréhension des algorithmes sous-jacents et des compromis abordés dans LINFO2345.
• LINFO2355 (Multicore programming) traite de la programmation concurrente en mémoire partagée, ainsi que des techniques de synchronisation et de mise à l’échelle sur une seule machine multicœur. LINFO2345 se concentre sur les systèmes à passage de messages. Les deux sujets sont hautement complémentaires mais font appel à des outils et techniques différents.

Ressources
en ligne

Page Moodle du cours (à retrouver avec le sigle LINFO2345).

Bibliographie

Mandatory course material on Moodle:

• Course slides
• Exercices 

Additional books and research papers may be suggested during the lectures but none are mandatory.

Faculté ou entité
en charge

> INFO