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


Home
• How to contact us
• How to apply
• Entrance requirements
• Management

The MPRI Programme
• Organisation
• Level 1 modules
• Level 2 modules

Practical information
• Calendar and timetable (2019/2020)
• Internships
• Scholarships
• PhD grants

Differences

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

Link to this comparison view

cours:c-2-18 [2011/07/12 19:26]
127.0.0.1 external edit 		cours:c-2-18 [2011/07/13 14:32] (current)
baptiste
Line 10: Line 10:
 ==== Plan du cours et intervenants prévus pour 2010-2011 ==== ==== Plan du cours et intervenants prévus pour 2010-2011 ====
  
- +
   -  Auto-stabilisation. (12h, Brigitte Rozoy   -  Auto-stabilisation. (12h, Brigitte Rozoy
   -  Preuves probabilistes d'auto-stabilisation (12h, Claudine Picaronny   -  Preuves probabilistes d'auto-stabilisation (12h, Claudine Picaronny
Line 23: Line 23:
 ==== Plan du cours ==== ==== Plan du cours ====
  
-<dt>Partie II : Auto-Stabilisation</dt> +=== Partie II : Auto-Stabilisation === 
-<dd>+ 
 **Cours 1**: **Cours 1**:
  
-  Introduction et définitions générales ( %ATTACHURL%/autostabilisation.pdf)+ Introduction et définitions générales ( %ATTACHURL%/autostabilisation.pdf)
  
-   * auto-stabilisation, pseudo-stabilisation, modèles de communication +  * auto-stabilisation, pseudo-stabilisation, modèles de communication 
-   * un exemple : le token-ring auto-stabilisant de Dijkstra +  * un exemple : le token-ring auto-stabilisant de Dijkstra 
  
 **Cours 2**: **Cours 2**:
  
-  Algorithmes auto-stabilisants classiques+ Algorithmes auto-stabilisants classiques
  
-   * orientation d'un anneau +  * orientation d'un anneau 
-   * maximal matching+  * maximal matching
  
 **Cours 3**: **Cours 3**:
  
-  Composition d'algorithmes+ Composition d'algorithmes
  
-   * méthodologie +  * méthodologie 
-   * arbres recouvrant et coloration+  * arbres recouvrant et coloration
  
 **Cours 4**: **Cours 4**:
  
-  Observation de l'auto-stabilisation+ Observation de l'auto-stabilisation
  
 ( %ATTACHURL%/Beauquier-Pilard-Rozoy-Disc05.pdf) ( %ATTACHURL%/Beauquier-Pilard-Rozoy-Disc05.pdf)
  
-   * déterministe+  * déterministe
  
-   * probabiliste+  * probabiliste
  
  
Line 60: Line 61:
 (%ATTACHURL%/MPRI-New-observabilit-Rozoy.doc) (%ATTACHURL%/MPRI-New-observabilit-Rozoy.doc)
  
-</dd> 
-<dt>Partie II : Preuves probabilistes d'auto-stabilisation </dt> 
-<dd> 
  
-**Cours 5**: +=== Partie II : Preuves probabilistes d'auto-stabilisation </dt> ===
  
- Introduction. Exemples.  
- Rappels de probabilités.  
  
 +**Cours 5**: 
 +
 +Introduction. Exemples. 
 +Rappels de probabilités. 
  
  
 (%ATTACHURL%/mpri//218//cours_5.pdf) (%ATTACHURL%/mpri//218//cours_5.pdf)
  
-  
  
 **Cours 6**: **Cours 6**:
-  Analyse qualitative (vérification de la propriété d'autostabilisation)+ Analyse qualitative (vérification de la propriété d'autostabilisation)
  
-   Le cas des adversaires sans mémoire  : chaînes de Markov. +Le cas des adversaires sans mémoire  : chaînes de Markov. 
-   Exemple :  l'algorithme de Hermann+Exemple :  l'algorithme de Hermann
  
 (%ATTACHURL%/cours//mpri//25octobre_2010.pdf) (%ATTACHURL%/cours//mpri//25octobre_2010.pdf)
  
-  
  
- **Cours 7**: 
  
- Le cas général : processus de décision markovien.   + **Cours 7**:
-  +
-   Exemples : L'algorithme d'Israeli et Jalfon +
- +
- autre exemple : l'algorithme de Kakugawa-Yamashita (%ATTACHURL%/kakugawa_yamashita.pdf|kakugawa_yamashita.pdf]): +
  
 +Le cas général : processus de décision markovien.  
 + 
 +Exemples : L'algorithme d'Israeli et Jalfon
  
 +autre exemple : l'algorithme de Kakugawa-Yamashita (%ATTACHURL%/kakugawa_yamashita.pdf|kakugawa_yamashita.pdf]): 
  
- Analyse quantitative (%ATTACHURL%/cours//mpri//8novembre_2010.pdf) 
  
-**Cours 8**: Des exemples. 
  
-  +Analyse quantitative (%ATTACHURL%/cours//mpri//8novembre_2010.pdf)
-  +
-</dd>+
  
 +**Cours 8**:Des exemples.
  
-<dt>Partie II : Tolérance aux pannes </dt>+=== Partie II : Tolérance aux pannes ===
  
-<dd> 
 **Cours 9**: **Cours 9**:
  
-  Introduction  générale : messages/mémoire partagée, synchrone/asynchrone+Introduction  générale : messages/mémoire partagée, synchrone/asynchrone
  
-  Introduction aux défaillances de liens+Introduction aux défaillances de liens 
 + 
 +Problème de l'attaque coordonnée (Lynch chapitre 5): 
 +  * impossibilité  
 +  * une solution non-déterministe
  
- Problème de l'attaque coordonnée (Lynch chapitre 5): 
-   * impossibilité  
-   * une solution non-déterministe 
-   
  
 **Cours 10, 11**: **Cours 10, 11**:
  
-  Consensus et TRB (terminating reliable broadcast) en synchrone avec des pannes par arrêt et par omissions:+Consensus et TRB (terminating reliable broadcast) en synchrone avec des pannes par arrêt et par omissions:
  
-   * algorithmes +  * algorithmes 
-   * borne sur la complexite du consensus( %ATTACHURL%/bivalency-ipl1999.pdf) +  * borne sur la complexite du consensus( %ATTACHURL%/bivalency-ipl1999.pdf) 
-   * algorithme à arrêt au plus tôt+  * algorithme à arrêt au plus tôt
  
 **Cours 11, 12**: **Cours 11, 12**:
  
- Consensus et TRB en synchrone et des pannes byzantines (Lynch Chapitre 6)+Consensus et TRB en synchrone et des pannes byzantines (Lynch Chapitre 6) 
 + 
 +  * avec  authentication (Pease, Shostak, Lamport) 
 +  * algorithme de l'EIG (exponential information gathering) 
 +  * impossibilité de réaliser un consensus byzantin avec moins de 2/3  tiers de corrects 
  
-   * avec  authentication (Pease, Shostak, Lamport) 
-   * algorithme de l'EIG (exponential information gathering) 
-   * impossibilité de réaliser un consensus byzantin avec moins de 2/3  tiers de corrects  
  
-  
 **Cours 13**: **Cours 13**:
-    +   
- Algorithme probabiliste de Ben Or en asynchrone avec des pannes par arrêt(%ATTACHURL%/TR98-1682.eps) +Algorithme probabiliste de Ben Or en asynchrone avec des pannes par arrêt(%ATTACHURL%/TR98-1682.eps) 
- Equivalence Atomic Brodcast et Consensus+Equivalence Atomic Brodcast et Consensus
  
  
Line 144: Line 137:
 **Cours 14**: **Cours 14**:
  
-  Impossibilité du consensus en asynchrone((%ATTACHURL%/FLP.pdf)+Impossibilité du consensus en asynchrone((%ATTACHURL%/FLP.pdf)
  
  
 **Cours 15, 16**: **Cours 15, 16**:
  
-  Détecteur de défaillances(%ATTACHURL%/CT-JACM96.pdf):+Détecteur de défaillances(%ATTACHURL%/CT-JACM96.pdf):
  
-   * détecteur Minimal pour le consensus: Omega ( %ATTACHURL%/CHT-JACM96.pdf): +  * détecteur Minimal pour le consensus: Omega ( %ATTACHURL%/CHT-JACM96.pdf): 
-   * implementation de Omega dans un système partiellement synchrone ( %ATTACHURL%/dc2008.pdf):+  * implementation de Omega dans un système partiellement synchrone ( %ATTACHURL%/dc2008.pdf):
  
-  Systèmes partiellement synchrones+Systèmes partiellement synchrones
  
 **Cours 17,18**: **Cours 17,18**:
  
-  Mémoire partagée:+Mémoire partagée:
  
-   * objets atomiques +  * objets atomiques 
-   * hiérarchie de Herlihy +  * hiérarchie de Herlihy 
-   * universalité du Consensus +  * universalité du Consensus
- +
- +
-</dd> +
- +
-</dl></html>+
  
 ==== Pré-requis ==== ==== Pré-requis ====
Line 179: Line 167:
 Partie I: Partie I:
  
- ** Gérard Tel, Introduction to Distributed Algorithm, chap. 17+** Gérard Tel, Introduction to Distributed Algorithm, chap. 17
  
- ** Shlomi Dolev, Self stabilization+** Shlomi Dolev, Self stabilization
  
 Partie II:  %ATTACHURL%/cours_mpri-2.18_bibliographie.pdf  Partie II:  %ATTACHURL%/cours_mpri-2.18_bibliographie.pdf 
  
-   * Kemeny, Snell.  //Finite Markov Chains//, Springer, 1976 +  * Kemeny, Snell.  //Finite Markov Chains//, Springer, 1976 
-   * Puterman. //Markov Decision Processes//,  Wiley, 1994 +  * Puterman. //Markov Decision Processes//,  Wiley, 1994 
-   * Baier, Katoen.  //Principles of Model Checking//,  MIT press, 2008+  * Baier, Katoen.  //Principles of Model Checking//,  MIT press, 2008
  
 Partie III: Partie III:
-   * Hagit Attiya, Jennifer Welch. _Distributed Computing Fundamentals, Simulations and Advanced Topics//Mc-Graw-Hill 1998. +  * Hagit Attiya, Jennifer Welch. _Distributed Computing Fundamentals, Simulations and Advanced Topics//Mc-Graw-Hill 1998. 
-   * Nancy A. Lynch.  _Distributed Algorithms.//Morgan Kaufmann, 1996. +  * Nancy A. Lynch.  _Distributed Algorithms.//Morgan Kaufmann, 1996. 
-   * Rachid Guerraoui, Luis Rodrigues. //Introduction to Reliable Distributed Programming// Springer 2008. +  * Rachid Guerraoui, Luis Rodrigues. //Introduction to Reliable Distributed Programming// Springer 2008. 
-   * Gadi Taubenfeld. //Synchronization Algorithms and Concurrent programming// Prentice hall 2006.+  * Gadi Taubenfeld. //Synchronization Algorithms and Concurrent programming// Prentice hall 2006.
  
-==== Les années précédentes ==== 
-   * [[2009-2010-C-2-18|Année 2009-2010]] 
-   * [[2008-2009-C-2-18|Année 2008-2009]] 
-   * [[2007-2008-C-2-18|Année 2007-2008]] 
-   * [[2006-2007-C-2-18|Année 2006-2007]] 
  
 ==== Équipe pédagogique ==== ==== Équipe pédagogique ====
Line 208: Line 191:
 |B. Rozoy|PU|Paris Sud|LRI| |B. Rozoy|PU|Paris Sud|LRI|
 |C. Picaronny|MC|ENS Cachan|LSV| |C. Picaronny|MC|ENS Cachan|LSV|
 +
 +/**
  
 ==== Notes de Cours ==== ==== Notes de Cours ====
-   * L. Fribourg, [[%ATTACHURL%/Laurent//Fribourg//Notes.pdf|Laurent//Fribourg//Notes.pdf]]: Notes de cours Nov 2007.+  * L. Fribourg, [[%ATTACHURL%/Laurent//Fribourg//Notes.pdf|Laurent//Fribourg//Notes.pdf]]: Notes de cours Nov 2007.
 ------ ------
-   * Set ALLOWTOPICCHANGE = %MAINWEB%.WebMastersGroup, %MAINWEB%.JoffroyBeauquier, %MAINWEB%.CaroleDelporte, %MAINWEB%.HuguesFauconnier, %MAINWEB%.LaurentFribourg, %MAINWEB%.ClaudinePicaronny, %MAINWEB%.BrigitteRozoy, +  * Set ALLOWTOPICCHANGE = %MAINWEB%.WebMastersGroup, %MAINWEB%.JoffroyBeauquier, %MAINWEB%.CaroleDelporte, %MAINWEB%.HuguesFauconnier, %MAINWEB%.LaurentFribourg, %MAINWEB%.ClaudinePicaronny, %MAINWEB%.BrigitteRozoy, 
-   * [[%ATTACHURL%/C-2-18.tex|C-2-18.tex]]: +  * [[%ATTACHURL%/C-2-18.tex|C-2-18.tex]]: 
  
-   * [[%ATTACHURL%/autostabilisation.pdf|autostabilisation.pdf]]: Autostabilisation 2009+  * [[%ATTACHURL%/autostabilisation.pdf|autostabilisation.pdf]]: Autostabilisation 2009
  
-   * [[%ATTACHURL%/MPRIobservabilitRozoy.doc|MPRIobservabilitRozoy.doc]]: Observation autostabilisation - schéma 2009+  * [[%ATTACHURL%/MPRIobservabilitRozoy.doc|MPRIobservabilitRozoy.doc]]: Observation autostabilisation - schéma 2009
  
-   * [[%ATTACHURL%/Beauquier-Pilard-Rozoy-Disc05.pdf|Beauquier-Pilard-Rozoy-Disc05.pdf]]: DISC 2005 observation probabiliste+  * [[%ATTACHURL%/Beauquier-Pilard-Rozoy-Disc05.pdf|Beauquier-Pilard-Rozoy-Disc05.pdf]]: DISC 2005 observation probabiliste
  
-   * [[%ATTACHURL%/MPRINewobservabilitRozoy.doc|MPRINewobservabilitRozoy.doc]]: Observabilité nouvelle version 02-01-2010+  * [[%ATTACHURL%/MPRINewobservabilitRozoy.doc|MPRINewobservabilitRozoy.doc]]: Observabilité nouvelle version 02-01-2010
  
-   * [[%ATTACHURL%/MPRI-New-observabilit-Rozoy.doc|MPRI-New-observabilit-Rozoy.doc]]: nouvelle version du précédent+  * [[%ATTACHURL%/MPRI-New-observabilit-Rozoy.doc|MPRI-New-observabilit-Rozoy.doc]]: nouvelle version du précédent
  
-   * [[%ATTACHURL%/Laurent//Fribourg//Notes.pdf|Laurent//Fribourg//Notes.pdf]]: Notes de cours 2007+  * [[%ATTACHURL%/Laurent//Fribourg//Notes.pdf|Laurent//Fribourg//Notes.pdf]]: Notes de cours 2007
  
-   * [[%ATTACHURL%/McIver-morgan.pdf|McIver-morgan.pdf]]: +  * [[%ATTACHURL%/McIver-morgan.pdf|McIver-morgan.pdf]]: 
  
-   * [[%ATTACHURL%/nakata.pdf|nakata.pdf]]: +  * [[%ATTACHURL%/nakata.pdf|nakata.pdf]]: 
  
-   * [[%ATTACHURL%/DFP.pdf|DFP.pdf]]: +  * [[%ATTACHURL%/DFP.pdf|DFP.pdf]]: 
  
-   * [[%ATTACHURL%/kakugawa_yamashita.pdf|kakugawa_yamashita.pdf]]: +  * [[%ATTACHURL%/kakugawa_yamashita.pdf|kakugawa_yamashita.pdf]]: 
  
-   * [[%ATTACHURL%/dcm.pdf|dcm.pdf]]: +  * [[%ATTACHURL%/dcm.pdf|dcm.pdf]]: 
  
-   * [[%ATTACHURL%/mpri//218//cours_5.pdf|mpri//218//cours_5.pdf]]: Résumé du cours 5+  * [[%ATTACHURL%/mpri//218//cours_5.pdf|mpri//218//cours_5.pdf]]: Résumé du cours 5
  
-   * [[%ATTACHURL%/cours_mpri-2.18_bibliographie.pdf|cours_mpri-2.18_bibliographie.pdf]]: Une bibliographie plus détaillée+  * [[%ATTACHURL%/cours_mpri-2.18_bibliographie.pdf|cours_mpri-2.18_bibliographie.pdf]]: Une bibliographie plus détaillée
  
-   * [[%ATTACHURL%/cours//mpri//8novembre_2010.pdf|cours//mpri//8novembre_2010.pdf]]: +  * [[%ATTACHURL%/cours//mpri//8novembre_2010.pdf|cours//mpri//8novembre_2010.pdf]]: 
  
 {{replaceme:C-2-18.tex|}} {{replaceme:C-2-18.tex|}}
Line 269: Line 254:
 {{replaceme:cours//mpri//25octobre_2010.pdf|}} {{replaceme:cours//mpri//25octobre_2010.pdf|}}
 {{replaceme:cours//mpri//8novembre_2010.pdf|}} {{replaceme:cours//mpri//8novembre_2010.pdf|}}
 +
 +**/
  
 
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