Algorithmique répartie

Master  IAP

2ème année semestre 2

Année 2018/19

DIDEL (inscrivez-vous!)
(M2AR2014)

Présentation:

Objectifs: Une introduction aux divers problèmes de l'algorithmique répartie. Il est conseillé de suivre aussi le cours de M2 programmation distribuée.

Plan (sous réserve...)

• Introduction:

• état global d'un système distribué. Exemple de la terminaison distribuée

• Algorithmes de vagues

• relation de causalité de Lamport
• algorithmes de vagues: exemple PIF, Resynch, calcul du minimum

• vagues sur un anneau, sur un arbre, algorithme de probe-echo, algorithme de phases

• snapshots

• Élections

• anneau
• autres topologies

• Réseaux anonymes

• algorithmes probabilistes: Monte-Carlo et Las Vegas
• élection - calcul de la taille

• Défaillances des liens

• problème de l'attaque coordonnée

• Défaillances des processus

• envoi-réception de messages en présence de défaillances des processus
• cas synchrone. Rondes synchronisées

• consensus pour des pannes crash: algorithme d'inondation
• généraux byzantins

• cas asynchrone et résultat d'impossibilité

• Extensions et perspectives

• implémenation registres, hiérarchie wait-free
• détecteur de défaillances.

Bibliographie :

            Tous ces livres vont bien au-delà des objectifs du cours !

Introduction to distributed algorithms	G. tel Cambridge
Distributed Algorithms	Nancy Lynch The Morgan Kaufmann Series in Data Management Systems
Introduction to Reliable Distributed Programming	Guerraoui, Rachid, Rodrigues, Luis Springer
Distributed Computing Fundamentals, Simulations, and Advanced Topics	Hagit Attiya et Jennifer Welch John Wiley and Sons, Inc.
Concurrent and Distributed Computing in Java	Vijay K. Garg Wiley & Sons, 2004
Distributed Computing: Principles, Algorithms, and Systems	Ajay D. Kshemkalyani,Mukesh Singhal (Cambridge)

Organisation

     Modalité de contrôle des connaissances 50% Contrôle continu (devoirs)  50% examen

L’enseignement est organisé en Cours - TD: Le responsable est Carole Delporte (Carole.Delporte[at] irif.fr). L'enseignement a lieu au deuxième trimestre. 

Jour	Heure	Salle
?	?	?

Calendrier (prévisions ou cours effectués suivant les dates)

Semaine	contenu	Remarque	Documents utiles pour ce cours
		r