University Sétif 1 FERHAT ABBAS Faculty of Sciences
Résultat de la recherche
1 résultat(s) recherche sur le mot-clé 'Réseaux Systèmes Distribués Systèmes répartis tolérance aux pannes auto-stabilisation arbres couvrants'
Ajouter le résultat dans votre panier Affiner la recherche Générer le flux rss de la recherche
Partager le résultat de cette recherche
Implémentation d'un algorithme auto-stabilisant pour le calcul d'un arbre couvrant / Bensedira,meriem
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 couvrantsIndex. 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 ................................................................................................ 54Côte titre : MAI/0135 En ligne : https://drive.google.com/file/d/1WDqzdpT3X98n5_y74vwIY9_Yq80iLFbX/view?usp=shari [...] Format de la ressource électronique : 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 couvrantsIndex. 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 ................................................................................................ 54Côte titre : MAI/0135 En ligne : https://drive.google.com/file/d/1WDqzdpT3X98n5_y74vwIY9_Yq80iLFbX/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0135 MAI/0135 Mémoire Bibliothéque des sciences Français Disponible
Disponible