University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'auteur
Auteur Belala,Linda |
Documents disponibles écrits par cet auteur
Ajouter le résultat dans votre panier Affiner la recherche
Titre : Un algorithme distribué auto-stabilisant pour le problème : " Maximal Open Packing Type de document : texte imprimé Auteurs : Belala,Linda, Auteur ; Guellati, Nabil, Directeur de thèse Editeur : Setif:UFA Année de publication : 2018 Importance : 1 vol (40 f .) Format : 29 cm Langues : Français (fre) Langues originales : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Auto-stabilisation
Tolérance aux pannes
Exclusion mutuelle
Paking
Démon,
Maximal open packing
Réseaux ordinaire
Réseaux en anneauxIndex. décimale : 004 - Informatique Résumé : Résumé
L’auto-stabilisation est l’une des techniques de tolérance aux pannes dans les systèmes
répartis qui consiste à retourner automatiquement à un fonctionnement correct au bout d’un
temps finis. Cette technique est faisable où l’intervention d’un humain pour rétablir le
système après une panne est impossible. Plusieurs algorithmes ont étaient développé en se
basent de cette propriété pour résoudre différents problèmes : exclusion mutuelle, maximal
2-paking...etc.
Dans les systèmes auto-stabilisant un mécanisme extérieur appelé démon (ordonnanceur)
est utilisé pour choisir les processus qui vont effectuer une action. Nous allons dans ce travail
développé un algorithme distribué auto-stabilisant pour le problème " maximal open packing
" qui utilise un démon central pour effectuéer les actions.Le problème de packing peut être
utiliser dans le clustring des réseaux Ainsi notre algorithme fonctionne pour une topologie
arbitraire.Note de contenu :
Sommaire
Table des matières
Liste des figures ii
Liste des tableaux iii
Introduction générale 1
1 Généralités sur les systèmes répartis 4
1.1 introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Systèmes répartis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.1 Objectif des systèmes distribués : . . . . . . . . . . . . . . . . . . . . . 5
1.2.2 Les topologies : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.3 Algorithmes distribués : . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.4 Les problèmes répartis : . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.5 Modèles de communication : . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Tolérance aux pannes : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4 Auto-stabilisation : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5 L’anneau à jeton de Dijkstra : . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.5.1 Réseau anonyme ou basé sur un identifiant : . . . . . . . . . . . . . . . 11
1.5.1.1 Les avantages et les inconvénients de l’auto-stabilisation : . . 11
1.6 Notions et Définitions : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.6.1 Demon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.7 Conclusion : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2 Etat de L’art 16
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2 Les clusters : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.1 Objectifs de la clusterisation : . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.2 Ensemble indépendant : . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.3 Notation : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3 Maximal 2-packing : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.1 Algorithmes auto stabilisant pour Maximal 2-packing : . . . . . . . . . 19
2.4 k-packing : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.4.1 Algorithme : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.4.2 Conclusion : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Table des matières
3 Algorithme auto-stabilisant pour le problème maximal open packing 29
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2 Maximal open packing : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2.1 Modèle du système : . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2.2 Description de l’algorithme : . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2.2.1 Preuve de correction : . . . . . . . . . . . . . . . . . . . . . . 34
3.2.3 Simulation et comparaison : . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2.3.1 Simulation : . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2.3.2 Comparaison : . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.3 Conclusion : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
Conclusion et Perspectives 37
BibliographieCôte titre : MAI/0243 En ligne : https://drive.google.com/file/d/1cCgGrrz__xUkFbeSVbfbK5VqF0ixl2LS/view?usp=shari [...] Format de la ressource électronique : Un algorithme distribué auto-stabilisant pour le problème : " Maximal Open Packing [texte imprimé] / Belala,Linda, Auteur ; Guellati, Nabil, Directeur de thèse . - [S.l.] : Setif:UFA, 2018 . - 1 vol (40 f .) ; 29 cm.
Langues : Français (fre) Langues originales : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Auto-stabilisation
Tolérance aux pannes
Exclusion mutuelle
Paking
Démon,
Maximal open packing
Réseaux ordinaire
Réseaux en anneauxIndex. décimale : 004 - Informatique Résumé : Résumé
L’auto-stabilisation est l’une des techniques de tolérance aux pannes dans les systèmes
répartis qui consiste à retourner automatiquement à un fonctionnement correct au bout d’un
temps finis. Cette technique est faisable où l’intervention d’un humain pour rétablir le
système après une panne est impossible. Plusieurs algorithmes ont étaient développé en se
basent de cette propriété pour résoudre différents problèmes : exclusion mutuelle, maximal
2-paking...etc.
Dans les systèmes auto-stabilisant un mécanisme extérieur appelé démon (ordonnanceur)
est utilisé pour choisir les processus qui vont effectuer une action. Nous allons dans ce travail
développé un algorithme distribué auto-stabilisant pour le problème " maximal open packing
" qui utilise un démon central pour effectuéer les actions.Le problème de packing peut être
utiliser dans le clustring des réseaux Ainsi notre algorithme fonctionne pour une topologie
arbitraire.Note de contenu :
Sommaire
Table des matières
Liste des figures ii
Liste des tableaux iii
Introduction générale 1
1 Généralités sur les systèmes répartis 4
1.1 introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Systèmes répartis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.1 Objectif des systèmes distribués : . . . . . . . . . . . . . . . . . . . . . 5
1.2.2 Les topologies : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.3 Algorithmes distribués : . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.4 Les problèmes répartis : . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.5 Modèles de communication : . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Tolérance aux pannes : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4 Auto-stabilisation : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5 L’anneau à jeton de Dijkstra : . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.5.1 Réseau anonyme ou basé sur un identifiant : . . . . . . . . . . . . . . . 11
1.5.1.1 Les avantages et les inconvénients de l’auto-stabilisation : . . 11
1.6 Notions et Définitions : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.6.1 Demon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.7 Conclusion : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2 Etat de L’art 16
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2 Les clusters : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.1 Objectifs de la clusterisation : . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.2 Ensemble indépendant : . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.3 Notation : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3 Maximal 2-packing : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.1 Algorithmes auto stabilisant pour Maximal 2-packing : . . . . . . . . . 19
2.4 k-packing : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.4.1 Algorithme : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.4.2 Conclusion : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Table des matières
3 Algorithme auto-stabilisant pour le problème maximal open packing 29
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2 Maximal open packing : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2.1 Modèle du système : . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2.2 Description de l’algorithme : . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2.2.1 Preuve de correction : . . . . . . . . . . . . . . . . . . . . . . 34
3.2.3 Simulation et comparaison : . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2.3.1 Simulation : . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2.3.2 Comparaison : . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.3 Conclusion : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
Conclusion et Perspectives 37
BibliographieCôte titre : MAI/0243 En ligne : https://drive.google.com/file/d/1cCgGrrz__xUkFbeSVbfbK5VqF0ixl2LS/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0243 MAI/0243 Mémoire Bibliothéque des sciences Français Disponible
Disponible
