Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

cours:c-2-17-2 [2011/07/12 19:26] (current)
Line 1: Line 1:
 +
 +===== Algorithmique distribuée pour les réseaux (24h, 3 ECTS) =====
 +
 +Responsable : Pierre Fraigniaud
 +
 +==== Langue du cours ====
 +
 +Le cours se déroulera en français, sauf s'il s'avère y avoir une forte demande pour l'anglais de la part de l'audience. 
 +
 +==== Objectifs ====
 +
 +Le cours est principalement motivé par l'importance croissante que prennent les "réseaux" dans nos capacités à véhiculer de l'information (Internet), à mettre cette information à disposition du public (la toile WWW), à échanger des contenus (pair-à-pair, réseaux sociaux), à communiquer en général (téléphonie mobile, réseaux sans fil), voire à propager des épidémies. 
 +
 +La démarche scientifique guidant le cours consistera à s'abstraire le plus possible des technologies utilisées pour se concentrer sur l'étude de phénomènes spécifiques partagés par un grand nombre des réseaux mentionnés ci-dessus. Il s'agira ainsi d'étudier des problèmes fondamentaux tels que la circulation ou la distribution de l'information, la complexité mémoire du routage, l'impact de la structure d'un réseau sur ses performances, etc.  
 +
 +Le cadre scientifique principal dans lequel s'inscrit ce type d'études est l'algorithmique distribuée,  permettant la conception et, surtout, l'analyse de protocoles mettant en oeuvre plusieurs entités en réseau travaillant concurremment à la réalisation d'une tâche. 
 +
 +==== Description générale du cours ====
 +
 +Le cours abordera les thèmes suivants :
 +
 +   * Structure des réseaux : décomposition, métriques, distance, l'exemple d'Internet.
 +
 +   * Diffusion : navigation dans les réseaux sociaux (phénomène "petit monde"), algorithmes épidémiques, protocoles de gossip. 
 +
 +   * Réseaux pair-à-pair : tables de hachage distribuées, distribution de contenu, streaming. 
 +
 +   * Réseaux logiques : spanners et l'exemple des multipoints relais dans les réseaux ad hoc. 
 +
 +   * Représentation implicite : étiquetage d'adjacence, étiquetage en distance, etc. 
 +
 +   * Routage : compacité, minimisation de la charge, etc.
 +
 +==== Description détaillées du cours 2010-2011 ====
 +
 +   * Navigation dans les réseaux sociaux : l'expérience de Milgram et les six degrés de séparation (petits mondes), le cas de réseaux en treillis réguliers et celui des réseaux de largeur arborescente borné. 
 +
 +   * Routage : problématique du routage compact, routage compact dans les arbres, bornes inférieures ; minimisation de la charge : le cas des graphes de Cayley. 
 +
 +   * Algorithmes déterministes de diffusion : problématique générale, algorithme optimal dans les arbres, algorithme optimal pour le modèle "arête disjoint", algorithme  d'approximation pour le modèle "sommet disjiont".
 +
 +   * Etiquetage et représentation implicite de graphes : adjacence, pour la relation ancêtre, étiquetage en distance, etc. 
 +
 +   * Théorie des "spanners" : construction de sous-réseaux couvrants (spanners) peu denses, applications au routage et à la conception de protocoles radio. 
 +
 +==== Intervenants du cours 2010-2011 ====
 +
 +P. Fraigniaud (Directeur de Recherche CNRS) et Laurent Viennot (Directeur de Recherche INRIA).
 +
 +==== Pré-requis ====
 +
 +Les étudiants souhaitant suivre ce cours sont invités à avoir suivi ou suivre en parallèle les cours "Algorithmique des graphes" (2-29-1) et "Fondements sur la modélisation des réseaux" (2-17-1). N'avoir pas suivi 2-29-1 et 2-17-1, ou ne pas suivre ces deux cours, ne compromet toutefois pas la possibilité de suivre 2-17-2. 
 +
 +==== Bibliographie ====
 +
 +La bibliographie ci-dessous contient une courte liste de livres de référence en algorithmique distribuée, en liaison étroite avec de nombreux concepts présentés dans ce cours. 
 +
 +   * David Peleg, Distributed Computing: A Locality-Sensitive Approach, SIAM, Philadelphia, PA, 2000.
 +
 +   * Nicola Santoro, Design and Analysis of Distributed Algorithms, Wiley 2006.
 +
 +   * Handbook of Graphs and Networks: From the Genome to the Internet. Stefan Bornholdt (Editor), Heinz Georg Schuster (Editor)
 +
 +   * R. Pastor-Satorras and A. Vespignani, Evolution and Structure of the Internet: A Statistical Physics Approach. (La traduction est parue chez Belin sous le titre "Internet : Structure et évolution"). 
 +
 +   * Béla Bollobàs, Random Graphs, Cambridge University Press, 2001 (2nd edition). 
 +
 +   * Svante Janson, Tomasz Luczak, and Andrzej Rucinski, Random Graphs by  (Wiley, 2000)
 +
 +   * Frank Thomson Leighton. Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann Publishers (1991). (La traduction est parue chez Morgan Kaufmann en 1995)
 +
 +   * Jean de Rumeur. Communication dans les réseaux de processeurs. Masson 1994. 
 +
 +==== Partiel et examen ====
 +
 +   * Partiel 17 novembre 2009: http://www.liafa.jussieu.fr/~pierref/MPRI/exam2010.pdf
 +   * Correction partiel 17 novembre 2009: http://www.liafa.jussieu.fr/~pierref/MPRI/correction_exam2010.pdf
 +
 +==== Equipe pédagogique ====
 +
 +P. Fraigniaud (Directeur de Recherche CNRS), Clémence Magnien (Chargée de Recherche CNRS), Laurent Massoulié (Directeur Thomson Lab, Paris), et Laurent Viennot (Directeur de Recherche INRIA).
 +
 +==== Les années précédentes ====
 +
 + ** Année  [[2009-2010-C-2-17-2|2009-2010]]
 +
 +
 +------
 +   * Set ALLOWTOPICCHANGE = %MAINWEB%.WebMastersGroup, %MAINWEB%.PierreFraigniaud, %MAINWEB%.LaurentMassoulie
 +
  
 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA