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-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