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 MEDS
Ré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é i
Côte titre :	MAI/0159
En ligne :	https://drive.google.com/file/d/1Aq_pR1_c9Qw66S3Ghk18_G5IDI48JpsU/view?usp=shari [...]
Format de la ressource électronique :	pdf

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 MEDS
Ré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é i
Côte titre :	MAI/0159
En ligne :	https://drive.google.com/file/d/1Aq_pR1_c9Qw66S3Ghk18_G5IDI48JpsU/view?usp=shari [...]
Format de la ressource électronique :	pdf