Un algorithme distribué auto-stabilisant pour calculer un ensemble fortement dominant minimal / BADAOUI, Mouna

Public ISBD 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

---

1 (1 - 1 / 1)