University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'auteur
Auteur Mahboub, abdelmouiz |
Documents disponibles écrits par cet auteur
Ajouter le résultat dans votre panier Affiner la recherche
Un nouvel algorithme auto-stabilisant pour le calcul de l'ensemble dominant étendu (Extended Dominating Set) / Mahboub, abdelmouiz
Titre : Un nouvel algorithme auto-stabilisant pour le calcul de l'ensemble dominant étendu (Extended Dominating Set) Type de document : texte imprimé Auteurs : Mahboub, abdelmouiz ; GUELLATI, N, Directeur de thèse Editeur : Setif:UFA Année de publication : 2017 Importance : 1 vol (53f.) 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 distribués
tolérance aux pannes
auto-stabilisation
clustering
ensemble dominant étendu minimal
MEDSRésumé : Résumé
Dans le contexte des systèmes distribués, la tolérance aux pannes est une nécessité
évidente. Dans ce projet n d'étude on s'intéresse à l'une des techniques de tolérance
aux pannes, connue sous le nom de l'auto-stabilisation. Cette technique garantit que
le système retrouve un comportement correct au bout d'un temps ni après avoir
été perturbé par une panne transitoire.
Ces systèmes sont aussi vulnérables au cout de communication qui peut être pallier par l'utilisation de clustering. Durant ce rapport on s'intéresse à développer un
algorithme de calcul d'un ensemble dominant, ce dernier est un algorithme uniforme
distribué et auto-stabilisant permettant de trouver un ensemble dominant étendu
minimal que nous appelons MEDS. Cet algorithme fonctionne dans les graphe arbitraire, suppose un démon centralisé et se base sur le modèle expression de Turau [18].
Note de contenu : Table des matières
Introduction générale 1
1 Systèmes distribués et Auto-Stabilisation 3
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Systèmes distribués . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1 Algorithmes distribués . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Les problèmes classiques des Algorithmes distribués . . . . . . 5
2.3 Modèle de communication . . . . . . . . . . . . . . . . . . . . 6
2.4 Tolérance aux pannes . . . . . . . . . . . . . . . . . . . . . . . 8
3 Auto stabilisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.1 Token ring de Dijkstra . . . . . . . . . . . . . . . . . . . . . . 10
3.2 Dénition formelle . . . . . . . . . . . . . . . . . . . . . . . . 12
3.2.1 système distribué . . . . . . . . . . . . . . . . . . . . 13
3.2.2 l'auto-stabilisation . . . . . . . . . . . . . . . . . . . 13
3.2.3 Correction . . . . . . . . . . . . . . . . . . . . . . . . 13
3.2.4 Convergence . . . . . . . . . . . . . . . . . . . . . . 13
3.3 Avantages et limites de l'auto-stabilisation . . . . . . . . . . . 13
3.4 Démons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2 Clusterisation dans les réseaux ad-hoc et les ensembles dominants 16
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2 Réseaux ad hoc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 Dénition formelle du Clustering . . . . . . . . . . . . . . . . 18
2.3 Formation des clusters dans un réseau ad hoc . . . . . . . . . 18
2.4 Cluster-Head . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.5 Les types de communication dans les réseaux ad hoc . . . . . 20
2.6 Les limites du Clustering . . . . . . . . . . . . . . . . . . . . . 21
2.7 Maintenance des clusters . . . . . . . . . . . . . . . . . . . . . 21
2.8 L'utilisation des "dominating set" dans le clustering . . . . . . 22
3 Etat de l'art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.1 Ensemble dominant . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2 Minimal total dominating set . . . . . . . . . . . . . . . . . . 24
3.2.1 MTDS . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.2.2 MTDS (modèle d'expression) . . . . . . . . . . . . . 25
3.3 Minimal K-dominating set . . . . . . . . . . . . . . . . . . . . 26
3.4 Minimal dominating set . . . . . . . . . . . . . . . . . . . . . 28
3.5 Minimal Weakly Connected Dominating Sets . . . . . . . . . . 31
4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3 Un nouvel algorithme auto-stabilisant pour calculer un "Minimal
Extended Dominating Set" 36
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2 Dénition de l'ensemble dominant étendu (Extended Dominating Set) 36
3 Présentation du modèle expression de Turau 2012 . . . . . . . . . . . 37
4 Présentation de notre algorithme auto-stabilisant pour le calcul d'un
MEDS (Minimal Extended Dominating Set) . . . . . . . . . . . . . . 38
4.1 Description de l'algorithme . . . . . . . . . . . . . . . . . . . . 38
4.2 Preuve de correction et de convergence . . . . . . . . . . . . . 39
4.2.1 Correction . . . . . . . . . . . . . . . . . . . . . . . . 39
5 Description du travail réalise . . . . . . . . . . . . . . . . . . . . . . . 39
5.1 Description de l'application de Lukasz Kuszner . . . . . . . . 40
5.2 Explication de la partie programmation de l'algorithme MEDS 42
5.3 La trace d'exécution . . . . . . . . . . . . . . . . . . . . . . . 45
5.3.1 Les Interfaces graphiques . . . . . . . . . . . . . . . 46
5.4 Simulation des algorithmes implémentés . . . . . . . . . . . . 47
5.4.1 Les détails de la simulation . . . . . . . . . . . . . . 47
5.4.2 Étude de performance . . . . . . . . . . . . . . . . . 48
6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
Conclusion générale 51
Résumé iCôte titre : MAI/0159 En ligne : https://drive.google.com/file/d/1Aq_pR1_c9Qw66S3Ghk18_G5IDI48JpsU/view?usp=shari [...] Format de la ressource électronique : Un nouvel algorithme auto-stabilisant pour le calcul de l'ensemble dominant étendu (Extended Dominating Set) [texte imprimé] / Mahboub, abdelmouiz ; GUELLATI, N, Directeur de thèse . - [S.l.] : Setif:UFA, 2017 . - 1 vol (53f.) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Réseaux
Systèmes Distribués
systèmes distribués
tolérance aux pannes
auto-stabilisation
clustering
ensemble dominant étendu minimal
MEDSRésumé : Résumé
Dans le contexte des systèmes distribués, la tolérance aux pannes est une nécessité
évidente. Dans ce projet n d'étude on s'intéresse à l'une des techniques de tolérance
aux pannes, connue sous le nom de l'auto-stabilisation. Cette technique garantit que
le système retrouve un comportement correct au bout d'un temps ni après avoir
été perturbé par une panne transitoire.
Ces systèmes sont aussi vulnérables au cout de communication qui peut être pallier par l'utilisation de clustering. Durant ce rapport on s'intéresse à développer un
algorithme de calcul d'un ensemble dominant, ce dernier est un algorithme uniforme
distribué et auto-stabilisant permettant de trouver un ensemble dominant étendu
minimal que nous appelons MEDS. Cet algorithme fonctionne dans les graphe arbitraire, suppose un démon centralisé et se base sur le modèle expression de Turau [18].
Note de contenu : Table des matières
Introduction générale 1
1 Systèmes distribués et Auto-Stabilisation 3
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Systèmes distribués . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1 Algorithmes distribués . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Les problèmes classiques des Algorithmes distribués . . . . . . 5
2.3 Modèle de communication . . . . . . . . . . . . . . . . . . . . 6
2.4 Tolérance aux pannes . . . . . . . . . . . . . . . . . . . . . . . 8
3 Auto stabilisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.1 Token ring de Dijkstra . . . . . . . . . . . . . . . . . . . . . . 10
3.2 Dénition formelle . . . . . . . . . . . . . . . . . . . . . . . . 12
3.2.1 système distribué . . . . . . . . . . . . . . . . . . . . 13
3.2.2 l'auto-stabilisation . . . . . . . . . . . . . . . . . . . 13
3.2.3 Correction . . . . . . . . . . . . . . . . . . . . . . . . 13
3.2.4 Convergence . . . . . . . . . . . . . . . . . . . . . . 13
3.3 Avantages et limites de l'auto-stabilisation . . . . . . . . . . . 13
3.4 Démons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2 Clusterisation dans les réseaux ad-hoc et les ensembles dominants 16
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2 Réseaux ad hoc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 Dénition formelle du Clustering . . . . . . . . . . . . . . . . 18
2.3 Formation des clusters dans un réseau ad hoc . . . . . . . . . 18
2.4 Cluster-Head . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.5 Les types de communication dans les réseaux ad hoc . . . . . 20
2.6 Les limites du Clustering . . . . . . . . . . . . . . . . . . . . . 21
2.7 Maintenance des clusters . . . . . . . . . . . . . . . . . . . . . 21
2.8 L'utilisation des "dominating set" dans le clustering . . . . . . 22
3 Etat de l'art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.1 Ensemble dominant . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2 Minimal total dominating set . . . . . . . . . . . . . . . . . . 24
3.2.1 MTDS . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.2.2 MTDS (modèle d'expression) . . . . . . . . . . . . . 25
3.3 Minimal K-dominating set . . . . . . . . . . . . . . . . . . . . 26
3.4 Minimal dominating set . . . . . . . . . . . . . . . . . . . . . 28
3.5 Minimal Weakly Connected Dominating Sets . . . . . . . . . . 31
4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3 Un nouvel algorithme auto-stabilisant pour calculer un "Minimal
Extended Dominating Set" 36
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2 Dénition de l'ensemble dominant étendu (Extended Dominating Set) 36
3 Présentation du modèle expression de Turau 2012 . . . . . . . . . . . 37
4 Présentation de notre algorithme auto-stabilisant pour le calcul d'un
MEDS (Minimal Extended Dominating Set) . . . . . . . . . . . . . . 38
4.1 Description de l'algorithme . . . . . . . . . . . . . . . . . . . . 38
4.2 Preuve de correction et de convergence . . . . . . . . . . . . . 39
4.2.1 Correction . . . . . . . . . . . . . . . . . . . . . . . . 39
5 Description du travail réalise . . . . . . . . . . . . . . . . . . . . . . . 39
5.1 Description de l'application de Lukasz Kuszner . . . . . . . . 40
5.2 Explication de la partie programmation de l'algorithme MEDS 42
5.3 La trace d'exécution . . . . . . . . . . . . . . . . . . . . . . . 45
5.3.1 Les Interfaces graphiques . . . . . . . . . . . . . . . 46
5.4 Simulation des algorithmes implémentés . . . . . . . . . . . . 47
5.4.1 Les détails de la simulation . . . . . . . . . . . . . . 47
5.4.2 Étude de performance . . . . . . . . . . . . . . . . . 48
6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
Conclusion générale 51
Résumé iCôte titre : MAI/0159 En ligne : https://drive.google.com/file/d/1Aq_pR1_c9Qw66S3Ghk18_G5IDI48JpsU/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0159 MAI/0159 Mémoire Bibliothéque des sciences Français Disponible
Disponible