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 |
| ==== 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 |
| ==== 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 |
| | | |
| | | |
| (%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 |
| | | |
| | | |
| **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 ==== |
| 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 ==== |
| |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|}} |
| {{replaceme:cours//mpri//25octobre_2010.pdf|}} | | {{replaceme:cours//mpri//25octobre_2010.pdf|}} |
| {{replaceme:cours//mpri//8novembre_2010.pdf|}} | | {{replaceme:cours//mpri//8novembre_2010.pdf|}} |
| + | |
| + | **/ |
| | | |