Algorithmique répartie

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.

• 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

Algorithmes de l'algorithme distribuée. Modèle avec envoi/réception de messages. Synchrone/asynchrone

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

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