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