Modèles et Algorithmes pour le Distribué (MAD)

Description

Ce module vise a poser les fondements des systemes et algorithmes repartis. On y developpe la notion centrale de concurrence (ou parallelisme) en montrant comment elle impacte la conception et la programmation de ces systemes, en les privant d'une notion de temps global. L'accent est mis sur la representation des executions de tels systemes sous forme d'ordres partiels d'evenements. On y montre comment modeliser et verifier de tels systemes, et comment developper des primitives de programmation pour garantir des proprietes globales, resistant a l'asynchronisme et aux pannes.

Mots-clés

Prérequis

Notions de base des langages formels (automates, langages, projections, produits, determinisation, automate minimal)

Mathematical requirements

Basics of formal languages (notions of automaton, language, projections, product, determinization, minimal automaton) Aucun

Contenu

Le cours comporte deux parties. La premiere porte sur les modeles de systemes repartis. On y developpe les notions d'interaction synchrone et asynchrone, en montrant qu'elles conduisent a des trajectoires dont les evenements sont partiellement ordonnes. Plusieurs modeles sont abordes pour representer de tels systemes: reseaux d'automates, et reseaux de Petri. Une semantique de concurrence vraie est introduite, via les traces de Mazurkiewicz et la notion de depliage. On montre ensuite comment verifier des proprietes simples sur de tels systemes. La seconde partie porte sur les algorithmes pour le reparti. On y developpe plusieurs abstractions de programmation comme l'exclusion mutuelle, differentes formes de diffusion, le consensus ou l'election. L'accent est aussi mis sur les notions de coherence des donnees reparties. Ces differentes briques sont ensuite assemblees pour montrer comment developper et analyser une block-chain.

Compétences acquises

Comment assembler des primitives de programmation vues en cours pour developper et analyser une block-chain (structure de base des monnaies electroniques telles que le bitcoin).

Enseignants

Eric Fabre (responsable), Emmanuelle Anceaume