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 auto-stabilisation arbre couvrant système distribué panne'
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
Titre : Implémentation d'un algorithme auto-stabilisant pour le calcul d'un arbre couvrant Type de document : texte imprimé Auteurs : Daikh, issam ; GUELLATI, N, Directeur de thèse Editeur : Setif:UFA Année de publication : 2017 Importance : 1 vol (43f.) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Réseaux
Systèmes Distribués
auto-stabilisation
arbre couvrant
système distribué
panneIndex. décimale : 004 Informatique Résumé : Résumé
Dans le contexte des réseaux a grande échelle, la prise en compte des pannes est une
nécessité évidente. Ce document s’intéresse a l’approche auto-stabilisante qui vise a
concevoir des algorithmes se réparant d’eux-même en cas de pannes transitoires. Dans
la littérature de l’auto-stabilisation, La structure de communication la plus utilisée est
souvent un arbre couvrant. La construction d’arbres couvrants participe a la résolution
de nombreux problèmes fondamentaux de l’algorithmique distribué. ce mémoire porte
plus particulièrement sur l’auto-stabilisation d’algorithmes distribués construisant des
structures couvrantes d’un système distribué.
Un grand nombre d’algorithmes auto-stabilisants pour la construction d’arbres couvrants
ont été proposés dans la littérature. Dans notre travail nous avons choisi un algorithme
et transformé du modèle théorique (hypothèses fortes) vers un modèle implémentable
(hypothèses réalistes), l’algorithme est implémenté sous JAVA en utilisant les sockets.Note de contenu : Table des matières
Introduction générale 1
1 Systèmes distribués et Auto-Stabilisation 3
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Systèmes distribués . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.1 Objectifs des systèmes distribués . . . . . . . . . . . . . . . . . . 4
1.2.2 Algorithmes distribués . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.3 Modèle de communication . . . . . . . . . . . . . . . . . . . . . . 6
1.2.4 Tolérance aux pannes . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Auto stabilisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3.1 Token ring de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3.2 Avantages de l’auto-stabilisation . . . . . . . . . . . . . . . . . . 11
1.3.3 Limites de l’auto-stabilisation . . . . . . . . . . . . . . . . . . . . 11
1.3.4 Démons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2 Algorithmes auto-stabilisants et arbres couvrants 13
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Arbres couvrants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.1 Arbres couvrants de poids minimum (MST) . . . . . . . . . . . . 14
2.2.2 Arbre de Steiner . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.3 Arbre couvrant de plus court chemin . . . . . . . . . . . . . . . . 16
2.3 Algorithmes auto-stabilisants . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3.1 Algorithme de NS Chen et Shing-Tsaan Huang . . . . . . . . . . 18
2.3.2 Algorithme de Sumit Sur et Pradip K Srimani . . . . . . . . . . . 19
2.3.3 Algorithme de Gheorghe Antonoiu et Pradip K Srimani . . . . . 21
2.3.4 Algorithme de S.Dolev, A.Israeli, S.Moran . . . . . . . . . . . . . 22
2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3 Construction d’arbre couvrant auto-stabilisante 25
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 Objectifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.3 Architecture Générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.4 Modélisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.4.1 Diagramme de classe . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.4.2 Diagrammes des séquences . . . . . . . . . . . . . . . . . . . . . 29
3.4.3 Diagramme états-transitions . . . . . . . . . . . . . . . . . . . . . 32
3.5 Environnement de développement . . . . . . . . . . . . . . . . . . . . . . 32
3.6 Choix du langage de programmation . . . . . . . . . . . . . . . . . . . . 32
3.7 Explication de la partie programmation de l’algorithme . . . . . . . . . . 32
3.8 Aperçu de l’application . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
Conclusion générale 41
Bibliography 43
Résumé 44Côte titre : MAI/0153 En ligne : https://drive.google.com/file/d/14nh0-KxaeKVP-YGGRLuOhkjQwhKR1WwG/view?usp=shari [...] Format de la ressource électronique : Implémentation d'un algorithme auto-stabilisant pour le calcul d'un arbre couvrant [texte imprimé] / Daikh, issam ; GUELLATI, N, Directeur de thèse . - [S.l.] : Setif:UFA, 2017 . - 1 vol (43f.) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Réseaux
Systèmes Distribués
auto-stabilisation
arbre couvrant
système distribué
panneIndex. décimale : 004 Informatique Résumé : Résumé
Dans le contexte des réseaux a grande échelle, la prise en compte des pannes est une
nécessité évidente. Ce document s’intéresse a l’approche auto-stabilisante qui vise a
concevoir des algorithmes se réparant d’eux-même en cas de pannes transitoires. Dans
la littérature de l’auto-stabilisation, La structure de communication la plus utilisée est
souvent un arbre couvrant. La construction d’arbres couvrants participe a la résolution
de nombreux problèmes fondamentaux de l’algorithmique distribué. ce mémoire porte
plus particulièrement sur l’auto-stabilisation d’algorithmes distribués construisant des
structures couvrantes d’un système distribué.
Un grand nombre d’algorithmes auto-stabilisants pour la construction d’arbres couvrants
ont été proposés dans la littérature. Dans notre travail nous avons choisi un algorithme
et transformé du modèle théorique (hypothèses fortes) vers un modèle implémentable
(hypothèses réalistes), l’algorithme est implémenté sous JAVA en utilisant les sockets.Note de contenu : Table des matières
Introduction générale 1
1 Systèmes distribués et Auto-Stabilisation 3
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Systèmes distribués . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.1 Objectifs des systèmes distribués . . . . . . . . . . . . . . . . . . 4
1.2.2 Algorithmes distribués . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.3 Modèle de communication . . . . . . . . . . . . . . . . . . . . . . 6
1.2.4 Tolérance aux pannes . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Auto stabilisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3.1 Token ring de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3.2 Avantages de l’auto-stabilisation . . . . . . . . . . . . . . . . . . 11
1.3.3 Limites de l’auto-stabilisation . . . . . . . . . . . . . . . . . . . . 11
1.3.4 Démons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2 Algorithmes auto-stabilisants et arbres couvrants 13
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Arbres couvrants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.1 Arbres couvrants de poids minimum (MST) . . . . . . . . . . . . 14
2.2.2 Arbre de Steiner . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.3 Arbre couvrant de plus court chemin . . . . . . . . . . . . . . . . 16
2.3 Algorithmes auto-stabilisants . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3.1 Algorithme de NS Chen et Shing-Tsaan Huang . . . . . . . . . . 18
2.3.2 Algorithme de Sumit Sur et Pradip K Srimani . . . . . . . . . . . 19
2.3.3 Algorithme de Gheorghe Antonoiu et Pradip K Srimani . . . . . 21
2.3.4 Algorithme de S.Dolev, A.Israeli, S.Moran . . . . . . . . . . . . . 22
2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3 Construction d’arbre couvrant auto-stabilisante 25
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 Objectifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.3 Architecture Générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.4 Modélisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.4.1 Diagramme de classe . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.4.2 Diagrammes des séquences . . . . . . . . . . . . . . . . . . . . . 29
3.4.3 Diagramme états-transitions . . . . . . . . . . . . . . . . . . . . . 32
3.5 Environnement de développement . . . . . . . . . . . . . . . . . . . . . . 32
3.6 Choix du langage de programmation . . . . . . . . . . . . . . . . . . . . 32
3.7 Explication de la partie programmation de l’algorithme . . . . . . . . . . 32
3.8 Aperçu de l’application . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
Conclusion générale 41
Bibliography 43
Résumé 44Côte titre : MAI/0153 En ligne : https://drive.google.com/file/d/14nh0-KxaeKVP-YGGRLuOhkjQwhKR1WwG/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0153 MAI/0153 Mémoire Bibliothéque des sciences Français Disponible
Disponible