University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'auteur
Auteur GUELLATI, N |
Documents disponibles écrits par cet auteur
Ajouter le résultat dans votre panier Affiner la recherche
Implémentation d'un algorithme auto-stabilisant pour le calcul d'un arbre couvrant / Bensedira,meriem
Titre : Implémentation d'un algorithme auto-stabilisant pour le calcul d'un arbre couvrant Type de document : texte imprimé Auteurs : Bensedira,meriem ; GUELLATI, N, Directeur de thèse Editeur : Setif:UFA Année de publication : 2016 Importance : 1 vol (55f.) 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 répartis
tolérance aux pannes
auto-stabilisation
arbres couvrantsIndex. décimale : 004 Informatique Résumé : Résumé
Les systèmes distribués sont particulièrement sujets à des pannes, lorsqu’on augmente le nombre de processeurs de tels systèmes, la possibilité que ces composants tombent en panne va être également élevée, l’auto-stabilisation est l’une des techniques de tolérance aux pannes
particulièrement les pannes transitoires.
En 1973, E.W. Dijkstra a définit l’auto-stabilisation comme la propriété pour un système de se retrouver lui-même dans un comportement correct en un nombre fini d’étapes, et ce, quel que soit son état initial. L’auto-stabilisation constitue donc un moyen efficace pour tolérer les pannes transitoires.
Notre étude a pour objectif alors de transformer et implémenter un algorithme autostabilisant permettant à un ensemble de nœuds d’un réseau, en démarrant d’une configuration
quelconque, d’arriver à une configuration correct, dite légitime, après un temps fini en
utilisant le modèle de communication par échange de messages.Note de contenu : Table des matières
INTRODUCTION GENERALE .......................................................................... 1
Chapitre 1: Systèmes distribués et auto-stabilisation
1.1 INTRODUCTION............................................................................................. 4
1.2 SYSTEMES DISTRIBUES ............................................................................................. 4
1.2.1 OBJECTIFS DES SYSTEMES DISTRIBUES ............................................................................. 5
1.2.2 LES MODES DE COMMUNICATIONS................................................................................ 5
1.2.3 ALGORITHMES DISTRIBUES ........................................................................................... 7
1.2.3.1 Problèmes classiques en algorithmique distribuée ....................................................................... 8
1.2.3.1.1 Les problèmes statiques............................................................................... 8
1.2.3.1.2 Les problèmes dynamiques ....................................................................... 8
1.2.3.2 Topologies classiques .................................................................................. 9
1.2.4 TOLERANCE AUX PANNES................................................................................. 9
1.2.4.1 Classification des pannes............................................................................. 10
1.2.4.2 Tolérance classique aux pannes ................................................................... 10
1.2.4.3 L’auto-stabilisation : ............................................................................. 11
1.2.4.3.1 Token-ring de Dijkstra...................................................................... 12
1.2.4.3.2 Définitions formelles........................................................................ 15
1.2.4.4 Atomicité :..................................................................................... 17
1.2.4.5 Démon :...................................................................................... 17
1.2.4.6 Complexité ............................................................................ 18
1.3. CONCLUSION .................................................19
Chapitre 2: Etat de l'art sur les algorithmes auto-stabilisants de calcul d'arbres couvrants
2.1 INTRODUCTION..................................................................................... 21
2.2 DEFINITIONS .......................................................................................... 21
2.3 ARBRES COUVRANTS ET PLUS COURT CHEMIN DANS LES SYSTEMES DISTRIBUES . 22
2.4 ALGORITHMES UTILISANT UN MODELE DE COMMUNICATION PAR MEMOIRE PARTAGEE ............................................ 23
2.4.1 ALGORITHMES UTILISANT UN DEMON CENTRALISE .............................................................................. 23
2.4.1.1 Algorithme de Huang et Chen.................................................................................... 23
2.4.1.2 Algorithme de Dolev, Israeli et Moran ......................................................................... 23
2.4.1.3 Algorithme de Dolev ......................................................................................... 24
2.4.1.4 Algorithme de Afek............................................................................................. 26
2.4.1.5 Algorithme de T.C.Huang ....................................................................................... 26
2.4.1.6 Algorithme de Lélia Blin...................................................................................... 28
2.4.1.7 Algorithme de Lélia Blin.................................................................................. 29
2.4.2 ALGORITHMES UTILISANT UN DEMON DISTRIBUE .................................................................. 31
2.4.2.1 Algorithme de Lavallé............................................................................... 31
2.4.2.2 Algorithme de T.C. Huang ................................................................................ 32
2.4.2.3 Algorithme de Lélia Blin.................................................................................. 34
2.5 ALGORITHMES UTILISANT UN MODELE DE COMMUNICATION PAR ECHANGE DE MESSAGES............................................. 35
2.5.1 ALGORITHME DE GUPTA ET SRIMANI .............................................................................. 35
6. CONCLUSION.............................................................................................. 36
Chapitre 3: conception et implémentation
3.1 INTRODUCTION....................................................................................... 38
3.2 TRANSFORMATION DE L’ALGORITHME AUTO-STABILISANT........................................... 38
3.2.1 LANGAGE DE PROGRAMMATION ET ENVIRONNEMENT..................................................................... 40
3.2.2 PRESENTATION DE L’ALGORITHME :............................................................................... 41
3.3 CONCEPTION ..................................................................................................... 43
3.3.1 SPECIFICATION INFORMELLE DES BESOINS ...................................................................... 43
3.3.2 MODELISATION ................................................................................................. 44
3.3.2.1 Modélisation des interactions..................................................................................... 44
3.3.2.2 Modélisation de la sémantique .............................................................................. 49
3.3.2.3 Modélisation de la structure ................................................................................... 49
3.4 SIMULATION D’UNE PANNE TRANSITOIRE .............................................................................. 50
3.5 CONCLUSION ......................................................................................................... 53
CONCLUSION GENERALE ................................................................................................ 54Côte titre : MAI/0135 En ligne : https://drive.google.com/file/d/1WDqzdpT3X98n5_y74vwIY9_Yq80iLFbX/view?usp=shari [...] Format de la ressource électronique : Implémentation d'un algorithme auto-stabilisant pour le calcul d'un arbre couvrant [texte imprimé] / Bensedira,meriem ; GUELLATI, N, Directeur de thèse . - [S.l.] : Setif:UFA, 2016 . - 1 vol (55f.) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Réseaux
Systèmes Distribués
Systèmes répartis
tolérance aux pannes
auto-stabilisation
arbres couvrantsIndex. décimale : 004 Informatique Résumé : Résumé
Les systèmes distribués sont particulièrement sujets à des pannes, lorsqu’on augmente le nombre de processeurs de tels systèmes, la possibilité que ces composants tombent en panne va être également élevée, l’auto-stabilisation est l’une des techniques de tolérance aux pannes
particulièrement les pannes transitoires.
En 1973, E.W. Dijkstra a définit l’auto-stabilisation comme la propriété pour un système de se retrouver lui-même dans un comportement correct en un nombre fini d’étapes, et ce, quel que soit son état initial. L’auto-stabilisation constitue donc un moyen efficace pour tolérer les pannes transitoires.
Notre étude a pour objectif alors de transformer et implémenter un algorithme autostabilisant permettant à un ensemble de nœuds d’un réseau, en démarrant d’une configuration
quelconque, d’arriver à une configuration correct, dite légitime, après un temps fini en
utilisant le modèle de communication par échange de messages.Note de contenu : Table des matières
INTRODUCTION GENERALE .......................................................................... 1
Chapitre 1: Systèmes distribués et auto-stabilisation
1.1 INTRODUCTION............................................................................................. 4
1.2 SYSTEMES DISTRIBUES ............................................................................................. 4
1.2.1 OBJECTIFS DES SYSTEMES DISTRIBUES ............................................................................. 5
1.2.2 LES MODES DE COMMUNICATIONS................................................................................ 5
1.2.3 ALGORITHMES DISTRIBUES ........................................................................................... 7
1.2.3.1 Problèmes classiques en algorithmique distribuée ....................................................................... 8
1.2.3.1.1 Les problèmes statiques............................................................................... 8
1.2.3.1.2 Les problèmes dynamiques ....................................................................... 8
1.2.3.2 Topologies classiques .................................................................................. 9
1.2.4 TOLERANCE AUX PANNES................................................................................. 9
1.2.4.1 Classification des pannes............................................................................. 10
1.2.4.2 Tolérance classique aux pannes ................................................................... 10
1.2.4.3 L’auto-stabilisation : ............................................................................. 11
1.2.4.3.1 Token-ring de Dijkstra...................................................................... 12
1.2.4.3.2 Définitions formelles........................................................................ 15
1.2.4.4 Atomicité :..................................................................................... 17
1.2.4.5 Démon :...................................................................................... 17
1.2.4.6 Complexité ............................................................................ 18
1.3. CONCLUSION .................................................19
Chapitre 2: Etat de l'art sur les algorithmes auto-stabilisants de calcul d'arbres couvrants
2.1 INTRODUCTION..................................................................................... 21
2.2 DEFINITIONS .......................................................................................... 21
2.3 ARBRES COUVRANTS ET PLUS COURT CHEMIN DANS LES SYSTEMES DISTRIBUES . 22
2.4 ALGORITHMES UTILISANT UN MODELE DE COMMUNICATION PAR MEMOIRE PARTAGEE ............................................ 23
2.4.1 ALGORITHMES UTILISANT UN DEMON CENTRALISE .............................................................................. 23
2.4.1.1 Algorithme de Huang et Chen.................................................................................... 23
2.4.1.2 Algorithme de Dolev, Israeli et Moran ......................................................................... 23
2.4.1.3 Algorithme de Dolev ......................................................................................... 24
2.4.1.4 Algorithme de Afek............................................................................................. 26
2.4.1.5 Algorithme de T.C.Huang ....................................................................................... 26
2.4.1.6 Algorithme de Lélia Blin...................................................................................... 28
2.4.1.7 Algorithme de Lélia Blin.................................................................................. 29
2.4.2 ALGORITHMES UTILISANT UN DEMON DISTRIBUE .................................................................. 31
2.4.2.1 Algorithme de Lavallé............................................................................... 31
2.4.2.2 Algorithme de T.C. Huang ................................................................................ 32
2.4.2.3 Algorithme de Lélia Blin.................................................................................. 34
2.5 ALGORITHMES UTILISANT UN MODELE DE COMMUNICATION PAR ECHANGE DE MESSAGES............................................. 35
2.5.1 ALGORITHME DE GUPTA ET SRIMANI .............................................................................. 35
6. CONCLUSION.............................................................................................. 36
Chapitre 3: conception et implémentation
3.1 INTRODUCTION....................................................................................... 38
3.2 TRANSFORMATION DE L’ALGORITHME AUTO-STABILISANT........................................... 38
3.2.1 LANGAGE DE PROGRAMMATION ET ENVIRONNEMENT..................................................................... 40
3.2.2 PRESENTATION DE L’ALGORITHME :............................................................................... 41
3.3 CONCEPTION ..................................................................................................... 43
3.3.1 SPECIFICATION INFORMELLE DES BESOINS ...................................................................... 43
3.3.2 MODELISATION ................................................................................................. 44
3.3.2.1 Modélisation des interactions..................................................................................... 44
3.3.2.2 Modélisation de la sémantique .............................................................................. 49
3.3.2.3 Modélisation de la structure ................................................................................... 49
3.4 SIMULATION D’UNE PANNE TRANSITOIRE .............................................................................. 50
3.5 CONCLUSION ......................................................................................................... 53
CONCLUSION GENERALE ................................................................................................ 54Côte titre : MAI/0135 En ligne : https://drive.google.com/file/d/1WDqzdpT3X98n5_y74vwIY9_Yq80iLFbX/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0135 MAI/0135 Mémoire Bibliothéque des sciences Français Disponible
Disponible
Titre : Implémentation d'un algorithme auto-stabilisant pour le calcul d'un arbre couvrant Type de document : texte imprimé Auteurs : Daikh, issam ; GUELLATI, N, Directeur de thèse Editeur : Setif:UFA Année de publication : 2017 Importance : 1 vol (43f.) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Réseaux
Systèmes Distribués
auto-stabilisation
arbre couvrant
système distribué
panneIndex. décimale : 004 Informatique Résumé : Résumé
Dans le contexte des réseaux a grande échelle, la prise en compte des pannes est une
nécessité évidente. Ce document s’intéresse a l’approche auto-stabilisante qui vise a
concevoir des algorithmes se réparant d’eux-même en cas de pannes transitoires. Dans
la littérature de l’auto-stabilisation, La structure de communication la plus utilisée est
souvent un arbre couvrant. La construction d’arbres couvrants participe a la résolution
de nombreux problèmes fondamentaux de l’algorithmique distribué. ce mémoire porte
plus particulièrement sur l’auto-stabilisation d’algorithmes distribués construisant des
structures couvrantes d’un système distribué.
Un grand nombre d’algorithmes auto-stabilisants pour la construction d’arbres couvrants
ont été proposés dans la littérature. Dans notre travail nous avons choisi un algorithme
et transformé du modèle théorique (hypothèses fortes) vers un modèle implémentable
(hypothèses réalistes), l’algorithme est implémenté sous JAVA en utilisant les sockets.Note de contenu : Table des matières
Introduction générale 1
1 Systèmes distribués et Auto-Stabilisation 3
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Systèmes distribués . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.1 Objectifs des systèmes distribués . . . . . . . . . . . . . . . . . . 4
1.2.2 Algorithmes distribués . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.3 Modèle de communication . . . . . . . . . . . . . . . . . . . . . . 6
1.2.4 Tolérance aux pannes . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Auto stabilisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3.1 Token ring de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3.2 Avantages de l’auto-stabilisation . . . . . . . . . . . . . . . . . . 11
1.3.3 Limites de l’auto-stabilisation . . . . . . . . . . . . . . . . . . . . 11
1.3.4 Démons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2 Algorithmes auto-stabilisants et arbres couvrants 13
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Arbres couvrants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.1 Arbres couvrants de poids minimum (MST) . . . . . . . . . . . . 14
2.2.2 Arbre de Steiner . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.3 Arbre couvrant de plus court chemin . . . . . . . . . . . . . . . . 16
2.3 Algorithmes auto-stabilisants . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3.1 Algorithme de NS Chen et Shing-Tsaan Huang . . . . . . . . . . 18
2.3.2 Algorithme de Sumit Sur et Pradip K Srimani . . . . . . . . . . . 19
2.3.3 Algorithme de Gheorghe Antonoiu et Pradip K Srimani . . . . . 21
2.3.4 Algorithme de S.Dolev, A.Israeli, S.Moran . . . . . . . . . . . . . 22
2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3 Construction d’arbre couvrant auto-stabilisante 25
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 Objectifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.3 Architecture Générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.4 Modélisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.4.1 Diagramme de classe . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.4.2 Diagrammes des séquences . . . . . . . . . . . . . . . . . . . . . 29
3.4.3 Diagramme états-transitions . . . . . . . . . . . . . . . . . . . . . 32
3.5 Environnement de développement . . . . . . . . . . . . . . . . . . . . . . 32
3.6 Choix du langage de programmation . . . . . . . . . . . . . . . . . . . . 32
3.7 Explication de la partie programmation de l’algorithme . . . . . . . . . . 32
3.8 Aperçu de l’application . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
Conclusion générale 41
Bibliography 43
Résumé 44Côte titre : MAI/0153 En ligne : https://drive.google.com/file/d/14nh0-KxaeKVP-YGGRLuOhkjQwhKR1WwG/view?usp=shari [...] Format de la ressource électronique : Implémentation d'un algorithme auto-stabilisant pour le calcul d'un arbre couvrant [texte imprimé] / Daikh, issam ; GUELLATI, N, Directeur de thèse . - [S.l.] : Setif:UFA, 2017 . - 1 vol (43f.) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Réseaux
Systèmes Distribués
auto-stabilisation
arbre couvrant
système distribué
panneIndex. décimale : 004 Informatique Résumé : Résumé
Dans le contexte des réseaux a grande échelle, la prise en compte des pannes est une
nécessité évidente. Ce document s’intéresse a l’approche auto-stabilisante qui vise a
concevoir des algorithmes se réparant d’eux-même en cas de pannes transitoires. Dans
la littérature de l’auto-stabilisation, La structure de communication la plus utilisée est
souvent un arbre couvrant. La construction d’arbres couvrants participe a la résolution
de nombreux problèmes fondamentaux de l’algorithmique distribué. ce mémoire porte
plus particulièrement sur l’auto-stabilisation d’algorithmes distribués construisant des
structures couvrantes d’un système distribué.
Un grand nombre d’algorithmes auto-stabilisants pour la construction d’arbres couvrants
ont été proposés dans la littérature. Dans notre travail nous avons choisi un algorithme
et transformé du modèle théorique (hypothèses fortes) vers un modèle implémentable
(hypothèses réalistes), l’algorithme est implémenté sous JAVA en utilisant les sockets.Note de contenu : Table des matières
Introduction générale 1
1 Systèmes distribués et Auto-Stabilisation 3
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Systèmes distribués . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.1 Objectifs des systèmes distribués . . . . . . . . . . . . . . . . . . 4
1.2.2 Algorithmes distribués . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.3 Modèle de communication . . . . . . . . . . . . . . . . . . . . . . 6
1.2.4 Tolérance aux pannes . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Auto stabilisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3.1 Token ring de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3.2 Avantages de l’auto-stabilisation . . . . . . . . . . . . . . . . . . 11
1.3.3 Limites de l’auto-stabilisation . . . . . . . . . . . . . . . . . . . . 11
1.3.4 Démons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2 Algorithmes auto-stabilisants et arbres couvrants 13
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Arbres couvrants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.1 Arbres couvrants de poids minimum (MST) . . . . . . . . . . . . 14
2.2.2 Arbre de Steiner . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.3 Arbre couvrant de plus court chemin . . . . . . . . . . . . . . . . 16
2.3 Algorithmes auto-stabilisants . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3.1 Algorithme de NS Chen et Shing-Tsaan Huang . . . . . . . . . . 18
2.3.2 Algorithme de Sumit Sur et Pradip K Srimani . . . . . . . . . . . 19
2.3.3 Algorithme de Gheorghe Antonoiu et Pradip K Srimani . . . . . 21
2.3.4 Algorithme de S.Dolev, A.Israeli, S.Moran . . . . . . . . . . . . . 22
2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3 Construction d’arbre couvrant auto-stabilisante 25
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 Objectifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.3 Architecture Générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.4 Modélisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.4.1 Diagramme de classe . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.4.2 Diagrammes des séquences . . . . . . . . . . . . . . . . . . . . . 29
3.4.3 Diagramme états-transitions . . . . . . . . . . . . . . . . . . . . . 32
3.5 Environnement de développement . . . . . . . . . . . . . . . . . . . . . . 32
3.6 Choix du langage de programmation . . . . . . . . . . . . . . . . . . . . 32
3.7 Explication de la partie programmation de l’algorithme . . . . . . . . . . 32
3.8 Aperçu de l’application . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
Conclusion générale 41
Bibliography 43
Résumé 44Côte titre : MAI/0153 En ligne : https://drive.google.com/file/d/14nh0-KxaeKVP-YGGRLuOhkjQwhKR1WwG/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0153 MAI/0153 Mémoire Bibliothéque des sciences Français Disponible
DisponibleImplémentation d'un algorithme auto-stabilisant pour le calcul d'un ensemble indépendant en utilisant la communication par messages / Bessou, mouhamed
Titre : Implémentation d'un algorithme auto-stabilisant pour le calcul d'un ensemble indépendant en utilisant la communication par messages Type de document : texte imprimé Auteurs : Bessou, mouhamed ; GUELLATI, N, Directeur de thèse Editeur : Setif:UFA Année de publication : 2017 Importance : 1 vol (50f.) 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éranceauxpannes
auto-stabilisation
clustering
ensemble indépendant maximalIndex. décimale : 004 Informatique Résumé : Résumé
Les progrès remarquables des équipements informatiques et de télécommunications durant ces dernières années ont permis une forte évolution de l'environnement distribué qui
les utilise. On est ainsi passé de réseaux locaux de stations de travail à des réseaux Ã
grande échelle. Cette avancée des équipements a permis de répondre plus ecacement aux
besoins des diérents domaines. La tolérance aux pannes dans les systèmes distribués est
un sujet qui a été largement étudié. La tolérance aux pannes fait référence à la capacité
d'un système de continuer à fonctionner lorsqu'une partie de celui-ci tombe en panne. Une
des solutions proposées pour la tolérance aux pannes est l'auto-stabilisation.
Ce mémoire étudie les algorithmes auto-stabilisants dans le cadre des systèmes distribués. Elle s'intéresse plus particulièrement à l'implémentation de ces algorithmes dans les
réseaux réels.
Dans la première partie, nous présentons le domaine des systèmes distribués, nous citons
leurs objectifs et les types des pannes qui les menaces. Nous présentons aussi l'approche
de l'auto-stabilisation en citons quelques-unes de ses avantages et ses limites.
Dans la deuxième partie, nous présentons les réseaux ad hoc, le clustering dans les
réseaux ad hoc et nous présentons aussi les ensembles indépendants en citons leur utilité
dans les réseaux. Nous terminons cette partie par la présentation de quelques algorithmes
auto-stabilisants permettant de calculés les ensembles indépendants maximaux.
Dans la troisième partie, nous essayons de surpasser les hypothèses fortes des algorithmes auto-stabilisants, pour cela nous proposons une solution pour utiliser l'algorithme
auto-stabilisant d'Ikeda dans un réseau réel. Finalement nous l'implémentons en langage
Java en utilisant les sockets.
Note de contenu : Table des matières
Introduction générale 1
1 Systèmes Distribués et Auto-Stabilisation 3
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Systèmes distribués . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 Objectifs des systèmes distribués . . . . . . . . . . . . . . . . 4
1.2.2 Algorithme distribué . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.3 Problème classique en algorithmique distribuée . . . . . . . . 5
1.3 Modèles de communications . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Tolérance au panne . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5 Auto Stabilisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.5.1 Token ring de Dijkstra . . . . . . . . . . . . . . . . . . . . . . 9
1.5.2 Avantages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.5.3 Inconvénients . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.5.4 Démon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2 Le clustering dans les réseaux ad-hoc et les ensembles indépendants 14
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2 Réseau ad hoc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2.1 La communication dans les réseaux ad hoc . . . . . . . . . . 15
2.2.2 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.3 Formation de clusters . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.4 Élection de cluster-head . . . . . . . . . . . . . . . . . . . . . 17
2.2.5 Maintenance des clusters . . . . . . . . . . . . . . . . . . . . . 17
2.2.6 Quelques approches de Clustering . . . . . . . . . . . . . . . . 17
2.3 Etat de l'art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.1 Les ensembles indépendants . . . . . . . . . . . . . . . . . . . 18
2.3.2 L'utilisation des ensembles indépendants maximaux (MIS) dans
le clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3.3 Algorithme de Shukla et al . . . . . . . . . . . . . . . . . . . . 19
2.3.4 Algorithme de Shi et al . . . . . . . . . . . . . . . . . . . . . . 20
2.3.5 Algorithme d'Ikeda et al . . . . . . . . . . . . . . . . . . . . . 21
2.3.6 Algorithme de Turau . . . . . . . . . . . . . . . . . . . . . . . 22
2.3.7 Algorithme de Goddard et al . . . . . . . . . . . . . . . . . . 23
2.3.8 Algorithme de Yen et Huang . . . . . . . . . . . . . . . . . . . 23
2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3 Implémentation de l'algorithme d'Ikeda dans un réseau réel 27
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2 Proposition d'une solution pour l'utilisation de l'algorithme d'Ikeda
dans les réseaux réels . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2.1 Algorithme d'Ikeda et al . . . . . . . . . . . . . . . . . . . . . 27
3.2.2 Algorithme transformé . . . . . . . . . . . . . . . . . . . . . . 28
3.3 Description de notre travail . . . . . . . . . . . . . . . . . . . . . . . 29
3.3.1 Modélisation avec UML . . . . . . . . . . . . . . . . . . . . . 30
3.4 Description du code Java . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.4.1 Le language Java . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.4.2 Socket . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.4.3 La classe ServeurdeNom . . . . . . . . . . . . . . . . . . . . . 36
3.4.4 La classe Résultat . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.4.5 Classe InfoVoisin . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.4.6 Classe N÷ud . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.5 Description de l'application . . . . . . . . . . . . . . . . . . . . . . . 41
3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
Conclusion générale 46Côte titre : MAI/0167 En ligne : https://drive.google.com/file/d/1OksvpU1oZBqDtH_YvMgebD-KIYf8bper/view?usp=shari [...] Format de la ressource électronique : Implémentation d'un algorithme auto-stabilisant pour le calcul d'un ensemble indépendant en utilisant la communication par messages [texte imprimé] / Bessou, mouhamed ; GUELLATI, N, Directeur de thèse . - [S.l.] : Setif:UFA, 2017 . - 1 vol (50f.) ; 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éranceauxpannes
auto-stabilisation
clustering
ensemble indépendant maximalIndex. décimale : 004 Informatique Résumé : Résumé
Les progrès remarquables des équipements informatiques et de télécommunications durant ces dernières années ont permis une forte évolution de l'environnement distribué qui
les utilise. On est ainsi passé de réseaux locaux de stations de travail à des réseaux Ã
grande échelle. Cette avancée des équipements a permis de répondre plus ecacement aux
besoins des diérents domaines. La tolérance aux pannes dans les systèmes distribués est
un sujet qui a été largement étudié. La tolérance aux pannes fait référence à la capacité
d'un système de continuer à fonctionner lorsqu'une partie de celui-ci tombe en panne. Une
des solutions proposées pour la tolérance aux pannes est l'auto-stabilisation.
Ce mémoire étudie les algorithmes auto-stabilisants dans le cadre des systèmes distribués. Elle s'intéresse plus particulièrement à l'implémentation de ces algorithmes dans les
réseaux réels.
Dans la première partie, nous présentons le domaine des systèmes distribués, nous citons
leurs objectifs et les types des pannes qui les menaces. Nous présentons aussi l'approche
de l'auto-stabilisation en citons quelques-unes de ses avantages et ses limites.
Dans la deuxième partie, nous présentons les réseaux ad hoc, le clustering dans les
réseaux ad hoc et nous présentons aussi les ensembles indépendants en citons leur utilité
dans les réseaux. Nous terminons cette partie par la présentation de quelques algorithmes
auto-stabilisants permettant de calculés les ensembles indépendants maximaux.
Dans la troisième partie, nous essayons de surpasser les hypothèses fortes des algorithmes auto-stabilisants, pour cela nous proposons une solution pour utiliser l'algorithme
auto-stabilisant d'Ikeda dans un réseau réel. Finalement nous l'implémentons en langage
Java en utilisant les sockets.
Note de contenu : Table des matières
Introduction générale 1
1 Systèmes Distribués et Auto-Stabilisation 3
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Systèmes distribués . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 Objectifs des systèmes distribués . . . . . . . . . . . . . . . . 4
1.2.2 Algorithme distribué . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.3 Problème classique en algorithmique distribuée . . . . . . . . 5
1.3 Modèles de communications . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Tolérance au panne . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5 Auto Stabilisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.5.1 Token ring de Dijkstra . . . . . . . . . . . . . . . . . . . . . . 9
1.5.2 Avantages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.5.3 Inconvénients . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.5.4 Démon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2 Le clustering dans les réseaux ad-hoc et les ensembles indépendants 14
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2 Réseau ad hoc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2.1 La communication dans les réseaux ad hoc . . . . . . . . . . 15
2.2.2 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.3 Formation de clusters . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.4 Élection de cluster-head . . . . . . . . . . . . . . . . . . . . . 17
2.2.5 Maintenance des clusters . . . . . . . . . . . . . . . . . . . . . 17
2.2.6 Quelques approches de Clustering . . . . . . . . . . . . . . . . 17
2.3 Etat de l'art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.1 Les ensembles indépendants . . . . . . . . . . . . . . . . . . . 18
2.3.2 L'utilisation des ensembles indépendants maximaux (MIS) dans
le clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3.3 Algorithme de Shukla et al . . . . . . . . . . . . . . . . . . . . 19
2.3.4 Algorithme de Shi et al . . . . . . . . . . . . . . . . . . . . . . 20
2.3.5 Algorithme d'Ikeda et al . . . . . . . . . . . . . . . . . . . . . 21
2.3.6 Algorithme de Turau . . . . . . . . . . . . . . . . . . . . . . . 22
2.3.7 Algorithme de Goddard et al . . . . . . . . . . . . . . . . . . 23
2.3.8 Algorithme de Yen et Huang . . . . . . . . . . . . . . . . . . . 23
2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3 Implémentation de l'algorithme d'Ikeda dans un réseau réel 27
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2 Proposition d'une solution pour l'utilisation de l'algorithme d'Ikeda
dans les réseaux réels . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2.1 Algorithme d'Ikeda et al . . . . . . . . . . . . . . . . . . . . . 27
3.2.2 Algorithme transformé . . . . . . . . . . . . . . . . . . . . . . 28
3.3 Description de notre travail . . . . . . . . . . . . . . . . . . . . . . . 29
3.3.1 Modélisation avec UML . . . . . . . . . . . . . . . . . . . . . 30
3.4 Description du code Java . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.4.1 Le language Java . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.4.2 Socket . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.4.3 La classe ServeurdeNom . . . . . . . . . . . . . . . . . . . . . 36
3.4.4 La classe Résultat . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.4.5 Classe InfoVoisin . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.4.6 Classe N÷ud . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.5 Description de l'application . . . . . . . . . . . . . . . . . . . . . . . 41
3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
Conclusion générale 46Côte titre : MAI/0167 En ligne : https://drive.google.com/file/d/1OksvpU1oZBqDtH_YvMgebD-KIYf8bper/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0167 MAI/0167 Mémoire Bibliothéque des sciences Français Disponible
DisponibleUn 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