Titre : |
Implémentation d'un algorithme auto-stabilisant pour le calcul d'un arbre couvrant |
Type de document : |
texte imprimé |
Auteurs : |
Bensedira,meriem ; GUELLATI, N, Directeur de thèse |
Editeur : |
Setif:UFA |
Année de publication : |
2016 |
Importance : |
1 vol (55f.) |
Format : |
29 cm |
Langues : |
Français (fre) |
Catégories : |
Thèses & Mémoires:Informatique
|
Mots-clés : |
Réseaux
Systèmes Distribués
Systèmes répartis
tolérance aux pannes
auto-stabilisation
arbres couvrants |
Index. décimale : |
004 Informatique |
Résumé : |
Résumé
Les systèmes distribués sont particulièrement sujets à des pannes, lorsqu’on augmente le nombre de processeurs de tels systèmes, la possibilité que ces composants tombent en panne va être également élevée, l’auto-stabilisation est l’une des techniques de tolérance aux pannes
particulièrement les pannes transitoires.
En 1973, E.W. Dijkstra a définit l’auto-stabilisation comme la propriété pour un système de se retrouver lui-même dans un comportement correct en un nombre fini d’étapes, et ce, quel que soit son état initial. L’auto-stabilisation constitue donc un moyen efficace pour tolérer les pannes transitoires.
Notre étude a pour objectif alors de transformer et implémenter un algorithme autostabilisant permettant à un ensemble de nœuds d’un réseau, en démarrant d’une configuration
quelconque, d’arriver à une configuration correct, dite légitime, après un temps fini en
utilisant le modèle de communication par échange de messages. |
Note de contenu : |
Table des matières
INTRODUCTION GENERALE .......................................................................... 1
Chapitre 1: Systèmes distribués et auto-stabilisation
1.1 INTRODUCTION............................................................................................. 4
1.2 SYSTEMES DISTRIBUES ............................................................................................. 4
1.2.1 OBJECTIFS DES SYSTEMES DISTRIBUES ............................................................................. 5
1.2.2 LES MODES DE COMMUNICATIONS................................................................................ 5
1.2.3 ALGORITHMES DISTRIBUES ........................................................................................... 7
1.2.3.1 Problèmes classiques en algorithmique distribuée ....................................................................... 8
1.2.3.1.1 Les problèmes statiques............................................................................... 8
1.2.3.1.2 Les problèmes dynamiques ....................................................................... 8
1.2.3.2 Topologies classiques .................................................................................. 9
1.2.4 TOLERANCE AUX PANNES................................................................................. 9
1.2.4.1 Classification des pannes............................................................................. 10
1.2.4.2 Tolérance classique aux pannes ................................................................... 10
1.2.4.3 L’auto-stabilisation : ............................................................................. 11
1.2.4.3.1 Token-ring de Dijkstra...................................................................... 12
1.2.4.3.2 Définitions formelles........................................................................ 15
1.2.4.4 Atomicité :..................................................................................... 17
1.2.4.5 Démon :...................................................................................... 17
1.2.4.6 Complexité ............................................................................ 18
1.3. CONCLUSION .................................................19
Chapitre 2: Etat de l'art sur les algorithmes auto-stabilisants de calcul d'arbres couvrants
2.1 INTRODUCTION..................................................................................... 21
2.2 DEFINITIONS .......................................................................................... 21
2.3 ARBRES COUVRANTS ET PLUS COURT CHEMIN DANS LES SYSTEMES DISTRIBUES . 22
2.4 ALGORITHMES UTILISANT UN MODELE DE COMMUNICATION PAR MEMOIRE PARTAGEE ............................................ 23
2.4.1 ALGORITHMES UTILISANT UN DEMON CENTRALISE .............................................................................. 23
2.4.1.1 Algorithme de Huang et Chen.................................................................................... 23
2.4.1.2 Algorithme de Dolev, Israeli et Moran ......................................................................... 23
2.4.1.3 Algorithme de Dolev ......................................................................................... 24
2.4.1.4 Algorithme de Afek............................................................................................. 26
2.4.1.5 Algorithme de T.C.Huang ....................................................................................... 26
2.4.1.6 Algorithme de Lélia Blin...................................................................................... 28
2.4.1.7 Algorithme de Lélia Blin.................................................................................. 29
2.4.2 ALGORITHMES UTILISANT UN DEMON DISTRIBUE .................................................................. 31
2.4.2.1 Algorithme de Lavallé............................................................................... 31
2.4.2.2 Algorithme de T.C. Huang ................................................................................ 32
2.4.2.3 Algorithme de Lélia Blin.................................................................................. 34
2.5 ALGORITHMES UTILISANT UN MODELE DE COMMUNICATION PAR ECHANGE DE MESSAGES............................................. 35
2.5.1 ALGORITHME DE GUPTA ET SRIMANI .............................................................................. 35
6. CONCLUSION.............................................................................................. 36
Chapitre 3: conception et implémentation
3.1 INTRODUCTION....................................................................................... 38
3.2 TRANSFORMATION DE L’ALGORITHME AUTO-STABILISANT........................................... 38
3.2.1 LANGAGE DE PROGRAMMATION ET ENVIRONNEMENT..................................................................... 40
3.2.2 PRESENTATION DE L’ALGORITHME :............................................................................... 41
3.3 CONCEPTION ..................................................................................................... 43
3.3.1 SPECIFICATION INFORMELLE DES BESOINS ...................................................................... 43
3.3.2 MODELISATION ................................................................................................. 44
3.3.2.1 Modélisation des interactions..................................................................................... 44
3.3.2.2 Modélisation de la sémantique .............................................................................. 49
3.3.2.3 Modélisation de la structure ................................................................................... 49
3.4 SIMULATION D’UNE PANNE TRANSITOIRE .............................................................................. 50
3.5 CONCLUSION ......................................................................................................... 53
CONCLUSION GENERALE ................................................................................................ 54 |
Côte titre : |
MAI/0135 |
En ligne : |
https://drive.google.com/file/d/1WDqzdpT3X98n5_y74vwIY9_Yq80iLFbX/view?usp=shari [...] |
Format de la ressource électronique : |
pdf |
Implémentation d'un algorithme auto-stabilisant pour le calcul d'un arbre couvrant [texte imprimé] / Bensedira,meriem ; GUELLATI, N, Directeur de thèse . - [S.l.] : Setif:UFA, 2016 . - 1 vol (55f.) ; 29 cm. Langues : Français ( fre)
Catégories : |
Thèses & Mémoires:Informatique
|
Mots-clés : |
Réseaux
Systèmes Distribués
Systèmes répartis
tolérance aux pannes
auto-stabilisation
arbres couvrants |
Index. décimale : |
004 Informatique |
Résumé : |
Résumé
Les systèmes distribués sont particulièrement sujets à des pannes, lorsqu’on augmente le nombre de processeurs de tels systèmes, la possibilité que ces composants tombent en panne va être également élevée, l’auto-stabilisation est l’une des techniques de tolérance aux pannes
particulièrement les pannes transitoires.
En 1973, E.W. Dijkstra a définit l’auto-stabilisation comme la propriété pour un système de se retrouver lui-même dans un comportement correct en un nombre fini d’étapes, et ce, quel que soit son état initial. L’auto-stabilisation constitue donc un moyen efficace pour tolérer les pannes transitoires.
Notre étude a pour objectif alors de transformer et implémenter un algorithme autostabilisant permettant à un ensemble de nœuds d’un réseau, en démarrant d’une configuration
quelconque, d’arriver à une configuration correct, dite légitime, après un temps fini en
utilisant le modèle de communication par échange de messages. |
Note de contenu : |
Table des matières
INTRODUCTION GENERALE .......................................................................... 1
Chapitre 1: Systèmes distribués et auto-stabilisation
1.1 INTRODUCTION............................................................................................. 4
1.2 SYSTEMES DISTRIBUES ............................................................................................. 4
1.2.1 OBJECTIFS DES SYSTEMES DISTRIBUES ............................................................................. 5
1.2.2 LES MODES DE COMMUNICATIONS................................................................................ 5
1.2.3 ALGORITHMES DISTRIBUES ........................................................................................... 7
1.2.3.1 Problèmes classiques en algorithmique distribuée ....................................................................... 8
1.2.3.1.1 Les problèmes statiques............................................................................... 8
1.2.3.1.2 Les problèmes dynamiques ....................................................................... 8
1.2.3.2 Topologies classiques .................................................................................. 9
1.2.4 TOLERANCE AUX PANNES................................................................................. 9
1.2.4.1 Classification des pannes............................................................................. 10
1.2.4.2 Tolérance classique aux pannes ................................................................... 10
1.2.4.3 L’auto-stabilisation : ............................................................................. 11
1.2.4.3.1 Token-ring de Dijkstra...................................................................... 12
1.2.4.3.2 Définitions formelles........................................................................ 15
1.2.4.4 Atomicité :..................................................................................... 17
1.2.4.5 Démon :...................................................................................... 17
1.2.4.6 Complexité ............................................................................ 18
1.3. CONCLUSION .................................................19
Chapitre 2: Etat de l'art sur les algorithmes auto-stabilisants de calcul d'arbres couvrants
2.1 INTRODUCTION..................................................................................... 21
2.2 DEFINITIONS .......................................................................................... 21
2.3 ARBRES COUVRANTS ET PLUS COURT CHEMIN DANS LES SYSTEMES DISTRIBUES . 22
2.4 ALGORITHMES UTILISANT UN MODELE DE COMMUNICATION PAR MEMOIRE PARTAGEE ............................................ 23
2.4.1 ALGORITHMES UTILISANT UN DEMON CENTRALISE .............................................................................. 23
2.4.1.1 Algorithme de Huang et Chen.................................................................................... 23
2.4.1.2 Algorithme de Dolev, Israeli et Moran ......................................................................... 23
2.4.1.3 Algorithme de Dolev ......................................................................................... 24
2.4.1.4 Algorithme de Afek............................................................................................. 26
2.4.1.5 Algorithme de T.C.Huang ....................................................................................... 26
2.4.1.6 Algorithme de Lélia Blin...................................................................................... 28
2.4.1.7 Algorithme de Lélia Blin.................................................................................. 29
2.4.2 ALGORITHMES UTILISANT UN DEMON DISTRIBUE .................................................................. 31
2.4.2.1 Algorithme de Lavallé............................................................................... 31
2.4.2.2 Algorithme de T.C. Huang ................................................................................ 32
2.4.2.3 Algorithme de Lélia Blin.................................................................................. 34
2.5 ALGORITHMES UTILISANT UN MODELE DE COMMUNICATION PAR ECHANGE DE MESSAGES............................................. 35
2.5.1 ALGORITHME DE GUPTA ET SRIMANI .............................................................................. 35
6. CONCLUSION.............................................................................................. 36
Chapitre 3: conception et implémentation
3.1 INTRODUCTION....................................................................................... 38
3.2 TRANSFORMATION DE L’ALGORITHME AUTO-STABILISANT........................................... 38
3.2.1 LANGAGE DE PROGRAMMATION ET ENVIRONNEMENT..................................................................... 40
3.2.2 PRESENTATION DE L’ALGORITHME :............................................................................... 41
3.3 CONCEPTION ..................................................................................................... 43
3.3.1 SPECIFICATION INFORMELLE DES BESOINS ...................................................................... 43
3.3.2 MODELISATION ................................................................................................. 44
3.3.2.1 Modélisation des interactions..................................................................................... 44
3.3.2.2 Modélisation de la sémantique .............................................................................. 49
3.3.2.3 Modélisation de la structure ................................................................................... 49
3.4 SIMULATION D’UNE PANNE TRANSITOIRE .............................................................................. 50
3.5 CONCLUSION ......................................................................................................... 53
CONCLUSION GENERALE ................................................................................................ 54 |
Côte titre : |
MAI/0135 |
En ligne : |
https://drive.google.com/file/d/1WDqzdpT3X98n5_y74vwIY9_Yq80iLFbX/view?usp=shari [...] |
Format de la ressource électronique : |
pdf |
|