Algorithmique répartie

Master Système Réseaux Internet

2ème année semestre 2

Année 2014

Présentation

Organisation

Calendrier

DIDEL (inscrivez-vous!)
(M2AR2014)

Premier devoir à rendre pour le 17 février
Deuxième devoir à rendre pour le 3 mars
Troisième devoir à rendre pour le 17 mars

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 et de traversée
  
• 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, algorithme de Finn
• algorithmes de traversées
• 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
• registres atomiques et 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
• 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 Hugues Fauconnier (Hugues.Fauconnier [at] liafa.jussieu.fr). L'enseignement a lieu au deuxième trimestre. 

Cours : Hugues Fauconnier

Jour	Heure	Salle
Lund	16h30-18h30	247E

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

Semaine	contenu	Remarque	Documents utiles pour ce cours
6 janvier	Introduction : exemple de la terminaison distribuée
13 janvier	Causalité, ordre de Lamport
20 janvier	Algorithmes de vagues définitions, algorihtm de l'arbre		introduction to distributed algorithms G.tel (chapitre 6)
27 janvier	Algorithmes de vagues arbre, probe-echo, gossip		introduction to distributed algorithms G.tel (chapitre 6)
3 février	Algorithmes de traversées (début)		introduction to distributed algorithms G.tel (chapitre 6)
10 février	Algorithmes de traversées, notion de temps d'exécution		introduction to distributed algorithms G.tel (chapitre 6)
17 février	Algorithmes d'élection	rendre premier devoir
24 février	Algorihtme d'élection Réseaux anonymes
3 mars		rendre deuxième devoir
10 mars
17 mars		rendre troisième devoir