University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'auteur
Auteur BADAOUI, Mouna |
Documents disponibles écrits par cet auteur
Ajouter le résultat dans votre panier Affiner la recherche
Un algorithme distribué auto-stabilisant pour calculer un ensemble fortement dominant minimal / BADAOUI, Mouna
Titre : Un algorithme distribué auto-stabilisant pour calculer un ensemble fortement dominant minimal Type de document : texte imprimé Auteurs : BADAOUI, Mouna ; SEMCHEDINE, FOUZI, Directeur de thèse Editeur : Setif:UFA Année de publication : 2015 Importance : 1 vol (69f.) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Système réparti, Tolérance aux pannes, Pannes transitoires, Auto-stabilisation, Ensemble dominant, Ensemble fortement dominant minimal. Index. décimale : 004 Informatique Résumé :
Résumé
Un système réparti est un système constitué d’un ensemble d’unités de calcul autonomes
dotées de capacités de communication. Ces unités coopèrent pour effectuer une tâche globale.
La probabilité que certains éléments du système subissent des pannes est non négligeable car
un système parfait sans pannes n’existe pas dans la réalité. Ces pannes peuvent être classifiées
en fonction de leur durée, de leur étendue et de leur nature. Plusieurs mécanismes de tolérance
aux pannes se présentent dans la littérature. Dans cette mémoire, nous nous intéressons Ã
l’auto-stabilisation qui est un mécanisme de tolérance aux pannes non masquant.
Les algorithmes auto-stabilisants de domination ont une application importante dans les
systèmes répartis qui est le clustering. Le clustering consiste au regroupement des nœuds selon
un ou plusieurs paramètres comme le degré du nœud, son poids, etc. Le clustering basé sur
le degré du nœud permet de construire des clusters denses. Dans ce mémoire nous présentons
un algorithme auto-stabilisant qui calcule un ensemble fortement dominant en utilisant un
démon centralisé en se basant sur l’algorithme de Hedetniemi. Nous présentons également la
transformation de cet algorithme en un autre qui utilise un démon distribué.
Note de contenu :
Table des matières
Liste des figures ii
Introduction générale 1
1 Introduction aux Systèmes Distribués et à l’Auto-stabilisation 4
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Les systèmes répartis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.2 Système réparti, réseau, système parallèle . . . . . . . . . . . . . . . . 6
1.2.2.1 Système réparti vs réseau . . . . . . . . . . . . . . . . . . . . 6
1.2.2.2 Système réparti vs système parallèle . . . . . . . . . . . . . . 6
1.2.3 Caractéristiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.4 Algorithmes distribués . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.5 Défis de conception . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.6 Modèles de communication . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.6.1 Le modèle de communication par échange de messages . . . . 9
1.2.6.2 Le modèle de communication par mémoire partagée . . . . . . 9
1.3 Tolérance aux pannes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.1 Taxonomie des pannes . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.1.1 Classification des pannes selon la localisation dans le temps . 11
1.3.1.2 Classification des pannes selon leur nature . . . . . . . . . . . 11
1.3.2 Les systèmes répartis et la tolérance aux pannes . . . . . . . . . . . . . 12
1.3.3 Mécanismes de tolérance aux pannes . . . . . . . . . . . . . . . . . . . 14
1.4 Auto-stabilisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.4.1 Comment prouver l’auto-stabilisation . . . . . . . . . . . . . . . . . . . 16
1.4.2 Token-ring de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.4.3 Algorithmes auto-stabilisants de graphes . . . . . . . . . . . . . . . . . 17
1.4.4 Propriétés des algorithmes d’auto-stabilisation . . . . . . . . . . . . . . 18
1.4.4.1 Avantages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.4.4.2 Inconvénients . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.4.5 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.4.6 Atomicité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.4.7 Démon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.4.8 Mesures de complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2 Algorithmes Auto-stabilisants de Calcul des Ensembles Dominants 24
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2 Notions de base de la théorie des graphes . . . . . . . . . . . . . . . . . . . . . 24
2.3 Le clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.4 Etat de l’art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.4.1 Algorithmes de calcul d’un ensemble dominant minimal (MDS) . . . . 30
2.4.2 Algorithmes de calcul d’un ensemble K-dominant minimal (MKDS) . . 39
2.4.3 Autres algorithmes de domination . . . . . . . . . . . . . . . . . . . . . 43
2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3 Un Algorithme Auto-stabilisant qui Calcule un MSDS 45
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.2 Un algorithme auto-stabilisant qui calcule un MSDS . . . . . . . . . . . . . . . 46
3.2.1 Hypothèses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.2.2 Proposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.2.3 Exemples d’exécution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.3 Preuve de correction et de convergence de l’algorithme proposé . . . . . . . . . 50
3.3.1 Preuve de correction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.3.2 Preuve de convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.4 Implémentation et simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.4.1 Implémentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.4.2 Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.4.2.1 Transformation . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.4.2.2 Résultats de simulation . . . . . . . . . . . . . . . . . . . . . 57
3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
Conclusion générale 63
Bibliographie 64
Annexes 67
A L’application de Kuszner 68
B Codes sources des algorithmes implémentés 70
Côte titre : MAI/0074 Un algorithme distribué auto-stabilisant pour calculer un ensemble fortement dominant minimal [texte imprimé] / BADAOUI, Mouna ; SEMCHEDINE, FOUZI, Directeur de thèse . - [S.l.] : Setif:UFA, 2015 . - 1 vol (69f.) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Système réparti, Tolérance aux pannes, Pannes transitoires, Auto-stabilisation, Ensemble dominant, Ensemble fortement dominant minimal. Index. décimale : 004 Informatique Résumé :
Résumé
Un système réparti est un système constitué d’un ensemble d’unités de calcul autonomes
dotées de capacités de communication. Ces unités coopèrent pour effectuer une tâche globale.
La probabilité que certains éléments du système subissent des pannes est non négligeable car
un système parfait sans pannes n’existe pas dans la réalité. Ces pannes peuvent être classifiées
en fonction de leur durée, de leur étendue et de leur nature. Plusieurs mécanismes de tolérance
aux pannes se présentent dans la littérature. Dans cette mémoire, nous nous intéressons Ã
l’auto-stabilisation qui est un mécanisme de tolérance aux pannes non masquant.
Les algorithmes auto-stabilisants de domination ont une application importante dans les
systèmes répartis qui est le clustering. Le clustering consiste au regroupement des nœuds selon
un ou plusieurs paramètres comme le degré du nœud, son poids, etc. Le clustering basé sur
le degré du nœud permet de construire des clusters denses. Dans ce mémoire nous présentons
un algorithme auto-stabilisant qui calcule un ensemble fortement dominant en utilisant un
démon centralisé en se basant sur l’algorithme de Hedetniemi. Nous présentons également la
transformation de cet algorithme en un autre qui utilise un démon distribué.
Note de contenu :
Table des matières
Liste des figures ii
Introduction générale 1
1 Introduction aux Systèmes Distribués et à l’Auto-stabilisation 4
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Les systèmes répartis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.2 Système réparti, réseau, système parallèle . . . . . . . . . . . . . . . . 6
1.2.2.1 Système réparti vs réseau . . . . . . . . . . . . . . . . . . . . 6
1.2.2.2 Système réparti vs système parallèle . . . . . . . . . . . . . . 6
1.2.3 Caractéristiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.4 Algorithmes distribués . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.5 Défis de conception . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.6 Modèles de communication . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.6.1 Le modèle de communication par échange de messages . . . . 9
1.2.6.2 Le modèle de communication par mémoire partagée . . . . . . 9
1.3 Tolérance aux pannes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.1 Taxonomie des pannes . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.1.1 Classification des pannes selon la localisation dans le temps . 11
1.3.1.2 Classification des pannes selon leur nature . . . . . . . . . . . 11
1.3.2 Les systèmes répartis et la tolérance aux pannes . . . . . . . . . . . . . 12
1.3.3 Mécanismes de tolérance aux pannes . . . . . . . . . . . . . . . . . . . 14
1.4 Auto-stabilisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.4.1 Comment prouver l’auto-stabilisation . . . . . . . . . . . . . . . . . . . 16
1.4.2 Token-ring de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.4.3 Algorithmes auto-stabilisants de graphes . . . . . . . . . . . . . . . . . 17
1.4.4 Propriétés des algorithmes d’auto-stabilisation . . . . . . . . . . . . . . 18
1.4.4.1 Avantages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.4.4.2 Inconvénients . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.4.5 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.4.6 Atomicité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.4.7 Démon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.4.8 Mesures de complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2 Algorithmes Auto-stabilisants de Calcul des Ensembles Dominants 24
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2 Notions de base de la théorie des graphes . . . . . . . . . . . . . . . . . . . . . 24
2.3 Le clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.4 Etat de l’art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.4.1 Algorithmes de calcul d’un ensemble dominant minimal (MDS) . . . . 30
2.4.2 Algorithmes de calcul d’un ensemble K-dominant minimal (MKDS) . . 39
2.4.3 Autres algorithmes de domination . . . . . . . . . . . . . . . . . . . . . 43
2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3 Un Algorithme Auto-stabilisant qui Calcule un MSDS 45
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.2 Un algorithme auto-stabilisant qui calcule un MSDS . . . . . . . . . . . . . . . 46
3.2.1 Hypothèses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.2.2 Proposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.2.3 Exemples d’exécution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.3 Preuve de correction et de convergence de l’algorithme proposé . . . . . . . . . 50
3.3.1 Preuve de correction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.3.2 Preuve de convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.4 Implémentation et simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.4.1 Implémentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.4.2 Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.4.2.1 Transformation . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.4.2.2 Résultats de simulation . . . . . . . . . . . . . . . . . . . . . 57
3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
Conclusion générale 63
Bibliographie 64
Annexes 67
A L’application de Kuszner 68
B Codes sources des algorithmes implémentés 70
Côte titre : MAI/0074 Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0074 MAI/0074 Mémoire Bibliothéque des sciences Français Disponible
Disponible