~~NOTOC~~

====== Algorithmique répartie ======

===== Description =====
Ce cours est une initiation aux problèmes de l'algorithmique répartie. Dans ce cours nous allons présenter certains des concepts de l'algorithmique répartie. Nous considérons surtout les modèles avec envoi/réception de messages (message passing) dans les systèmes asynchrones. Dans une première partie on considère les problèmes classiques qui reviennent souvent à reconstituer un état global du sytème à partir d'états locaux connus des processus. Dans un deuxième temps on s'intéresse aux défaillances et aux problèmes d'accord en présence de défaillances.


===== Syllabus =====
  * Introduction et présentation générale
  * Partie I: algorithmes classiques
    * Construire un état global à partir d’états locaux
    * Exemple de la terminaison distribuée
    * Algorithmes de vagues et de traversée, probe-echo, gossip etc…
    * Snapshot
    * Election de leader
    * Réseaux anonymes,  élection probabiliste 
    * Introduction à l’auto-stabilisation: protocole du bit alterné
  * Partie II: algorithmique tolérante aux pannes
    * Défaillances des liens de communications: attaque coordonnée
    * Modèle synchrone avec défaillances de processus
       * Consensus
       * Accord byzantin
       * « commit »: 2-phase et 3-phase commit
    * Modèle asynchrone avec défaillances
       * Diffusion fiable, diffusion atomique
       * Impossibilité du consensus et ses conséquences 
  
==== Sujets centraux ====
Algorithmes de l'algorithme distribuée.
Modèle avec envoi/réception de messages.
Synchrone/asynchrone




==== Sujets potentiellement traités ====
Problème de la construction d'un état globe du système à partir des états locau.
Problème de l'accord en présence de défaillances

===== Pré-requis =====
Aucun pré-requis, mais des connaissances en réseau sont utiles. Il est fortement recommandé de suivre aussi l'enseignement de [[progrepar10|Programmation Répartie]] du master qui présente une vision complémentaire de ce cours