University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'auteur
Auteur Yousra Touahra |
Documents disponibles écrits par cet auteur
Ajouter le résultat dans votre panier Affiner la recherche
Titre : Un nouvel algorithme auto-stabilisant pour le calcul d’un ensemble 1-isolé Type de document : document électronique Auteurs : Yousra Touahra, Auteur ; Imane Derradj, Auteur ; Nabil Guellati, Directeur de thèse Editeur : Sétif:UFA1 Année de publication : 2024 Importance : 1 vol (46 f .) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Auto-stabilisation
Systèmes distribués
Algorithmes distribués
Ensembles indépendants
Ensembles 1-isolésIndex. décimale : 004 Informatique Résumé :
L’auto-stabilisation est une méthode permettant de gérer les pannes transitoires,
introduite par Dijkstra. Un système distribué est considéré comme auto-stabilisant s’il
est capable de revenir à un état correct après une période de temps fini, quel que soit
son état initial. Plusieurs problématiques observées dans les réseaux et les systèmes
distribués peuvent être modélisés à l’aide de graphes. Notre étude se concentre sur les
algorithmes distribués auto-stabilisants qui facilitent le calcul des ensembles indépendants
et dominants dans un graphe. Nous présentons un nouvel algorithme distribué
auto-stabilisant permettant de calculer un ensemble 1-isolé (TKD-1IS : 1-insulated set)
dans un graphe quelconque. Nous évaluons ses performances en simulant son comportement
dans un environnement à grande échelle. En outre, nous comparons notre
algorithme à d’autres algorithmes similaires de la littérature et discutons des résultats
obtenus, aussi nous présentons deux nouvelles versions de notre algorithme. Ce dernier
peut être utilisé pour organiser les ressources dans un système distribué et s’avère utile
pour regrouper des noeuds dans des réseaux (clustering).Note de contenu :
Sommaire
Introduction générale 1
1 Les systèmes distribués et l’auto-stabilisation 3
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Les systèmes distribués . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 Exemples de systèmes distribués célèbres . . . . . . . . . . . . . 3
1.2.2 Les avantages des systemes distribués . . . . . . . . . . . . . . . 4
1.2.3 Les algorithmes distribués . . . . . . . . . . . . . . . . . . . . . 4
1.3 Les graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3.2 Types de graphes . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Les pannes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4.1 Les types de pannes . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4.2 La tolérance aux pannes . . . . . . . . . . . . . . . . . . . . . . 6
1.5 L’auto-stabilisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5.1 Définition : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5.2 Exemple d’algorithme auto-stabilisant . . . . . . . . . . . . . . 8
1.5.3 Les avantages de l’auto-stabilisation . . . . . . . . . . . . . . . 10
1.5.4 Les inconvénients de l’auto-stabilisation . . . . . . . . . . . . . 10
1.5.5 Les démons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.5.6 Preuve d’auto-stabilisation . . . . . . . . . . . . . . . . . . . . 11
1.5.6.1 Preuve de Correction . . . . . . . . . . . . . . . . . . . 11
1.5.6.2 Preuve de Convergence . . . . . . . . . . . . . . . . . 11
1.5.7 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.5.7.1 Complexité en espace : . . . . . . . . . . . . . . . . . . 11
1.5.7.2 Complexité en temps . . . . . . . . . . . . . . . . . . 11
1.6 Définitions formelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2 Algorithmes d’ensembles indépendants 13
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.1 Les ensembles dominants . . . . . . . . . . . . . . . . . . . . . . 13
2.2.2 Les ensembles indépendants . . . . . . . . . . . . . . . . . . . . 14
2.2.3 Les ensembles k-isolés . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.4 Les ensembles 1-isolés . . . . . . . . . . . . . . . . . . . . . . . 15
2.3 Le clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3.1 définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3.2 Les avantages du clustering . . . . . . . . . . . . . . . . . . . . 16
2.3.3 Usage des ensembles indépendants dans le clustering . . . . . . 17
2.4 L’état de l’art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.4.1 Algorithme de Hedetniemi . . . . . . . . . . . . . . . . . . . . . 18
2.4.2 Algorithme de Turau . . . . . . . . . . . . . . . . . . . . . . . . 19
2.4.3 Algorithme de Shukla . . . . . . . . . . . . . . . . . . . . . . . . 21
2.4.4 Algorithme de Srimani . . . . . . . . . . . . . . . . . . . . . . . 22
2.4.5 Algorithme de Naggazi . . . . . . . . . . . . . . . . . . . . . . . 24
2.4.6 Algorithme de Michiyo . . . . . . . . . . . . . . . . . . . . . . . 25
2.4.7 Récapitulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.5 Autres références . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3 Un nouvel algorithme auto-stabilisant pour le calcul d’un ensemble
1-isolé (1-insulated set) 30
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.3 Hypothèses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.4 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.5 Les règles de l’algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.6 Preuve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.6.1 Preuve de correction . . . . . . . . . . . . . . . . . . . . . . . . 33
3.6.2 Preuve de convergence . . . . . . . . . . . . . . . . . . . . . . . 33
3.7 Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.8 Interface de l’application . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.9 Description du code de l’application de Kuszner (avec nos modifications) 37
3.10 Description de la première transformation (TKD_1IS_V2) . . . . . . . 41
3.11 Les règles de TKD_1IS_V2 . . . . . . . . . . . . . . . . . . . . . . . . 42
3.12 Description de la deuxième transformation (TKD_1IS_V3) . . . . . . . 43
3.13 Les règles de TKD_1IS_V3 . . . . . . . . . . . . . . . . . . . . . . . . 43
3.14 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
Conclusion générale 44Côte titre : MAI/0943 Un nouvel algorithme auto-stabilisant pour le calcul d’un ensemble 1-isolé [document électronique] / Yousra Touahra, Auteur ; Imane Derradj, Auteur ; Nabil Guellati, Directeur de thèse . - [S.l.] : Sétif:UFA1, 2024 . - 1 vol (46 f .) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Auto-stabilisation
Systèmes distribués
Algorithmes distribués
Ensembles indépendants
Ensembles 1-isolésIndex. décimale : 004 Informatique Résumé :
L’auto-stabilisation est une méthode permettant de gérer les pannes transitoires,
introduite par Dijkstra. Un système distribué est considéré comme auto-stabilisant s’il
est capable de revenir à un état correct après une période de temps fini, quel que soit
son état initial. Plusieurs problématiques observées dans les réseaux et les systèmes
distribués peuvent être modélisés à l’aide de graphes. Notre étude se concentre sur les
algorithmes distribués auto-stabilisants qui facilitent le calcul des ensembles indépendants
et dominants dans un graphe. Nous présentons un nouvel algorithme distribué
auto-stabilisant permettant de calculer un ensemble 1-isolé (TKD-1IS : 1-insulated set)
dans un graphe quelconque. Nous évaluons ses performances en simulant son comportement
dans un environnement à grande échelle. En outre, nous comparons notre
algorithme à d’autres algorithmes similaires de la littérature et discutons des résultats
obtenus, aussi nous présentons deux nouvelles versions de notre algorithme. Ce dernier
peut être utilisé pour organiser les ressources dans un système distribué et s’avère utile
pour regrouper des noeuds dans des réseaux (clustering).Note de contenu :
Sommaire
Introduction générale 1
1 Les systèmes distribués et l’auto-stabilisation 3
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Les systèmes distribués . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 Exemples de systèmes distribués célèbres . . . . . . . . . . . . . 3
1.2.2 Les avantages des systemes distribués . . . . . . . . . . . . . . . 4
1.2.3 Les algorithmes distribués . . . . . . . . . . . . . . . . . . . . . 4
1.3 Les graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3.2 Types de graphes . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Les pannes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4.1 Les types de pannes . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4.2 La tolérance aux pannes . . . . . . . . . . . . . . . . . . . . . . 6
1.5 L’auto-stabilisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5.1 Définition : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5.2 Exemple d’algorithme auto-stabilisant . . . . . . . . . . . . . . 8
1.5.3 Les avantages de l’auto-stabilisation . . . . . . . . . . . . . . . 10
1.5.4 Les inconvénients de l’auto-stabilisation . . . . . . . . . . . . . 10
1.5.5 Les démons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.5.6 Preuve d’auto-stabilisation . . . . . . . . . . . . . . . . . . . . 11
1.5.6.1 Preuve de Correction . . . . . . . . . . . . . . . . . . . 11
1.5.6.2 Preuve de Convergence . . . . . . . . . . . . . . . . . 11
1.5.7 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.5.7.1 Complexité en espace : . . . . . . . . . . . . . . . . . . 11
1.5.7.2 Complexité en temps . . . . . . . . . . . . . . . . . . 11
1.6 Définitions formelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2 Algorithmes d’ensembles indépendants 13
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.1 Les ensembles dominants . . . . . . . . . . . . . . . . . . . . . . 13
2.2.2 Les ensembles indépendants . . . . . . . . . . . . . . . . . . . . 14
2.2.3 Les ensembles k-isolés . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.4 Les ensembles 1-isolés . . . . . . . . . . . . . . . . . . . . . . . 15
2.3 Le clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3.1 définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3.2 Les avantages du clustering . . . . . . . . . . . . . . . . . . . . 16
2.3.3 Usage des ensembles indépendants dans le clustering . . . . . . 17
2.4 L’état de l’art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.4.1 Algorithme de Hedetniemi . . . . . . . . . . . . . . . . . . . . . 18
2.4.2 Algorithme de Turau . . . . . . . . . . . . . . . . . . . . . . . . 19
2.4.3 Algorithme de Shukla . . . . . . . . . . . . . . . . . . . . . . . . 21
2.4.4 Algorithme de Srimani . . . . . . . . . . . . . . . . . . . . . . . 22
2.4.5 Algorithme de Naggazi . . . . . . . . . . . . . . . . . . . . . . . 24
2.4.6 Algorithme de Michiyo . . . . . . . . . . . . . . . . . . . . . . . 25
2.4.7 Récapitulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.5 Autres références . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3 Un nouvel algorithme auto-stabilisant pour le calcul d’un ensemble
1-isolé (1-insulated set) 30
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.3 Hypothèses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.4 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.5 Les règles de l’algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.6 Preuve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.6.1 Preuve de correction . . . . . . . . . . . . . . . . . . . . . . . . 33
3.6.2 Preuve de convergence . . . . . . . . . . . . . . . . . . . . . . . 33
3.7 Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.8 Interface de l’application . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.9 Description du code de l’application de Kuszner (avec nos modifications) 37
3.10 Description de la première transformation (TKD_1IS_V2) . . . . . . . 41
3.11 Les règles de TKD_1IS_V2 . . . . . . . . . . . . . . . . . . . . . . . . 42
3.12 Description de la deuxième transformation (TKD_1IS_V3) . . . . . . . 43
3.13 Les règles de TKD_1IS_V3 . . . . . . . . . . . . . . . . . . . . . . . . 43
3.14 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
Conclusion générale 44Côte titre : MAI/0943 Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0943 MAI/0943 Mémoire Bibliothéque des sciences Français Disponible
Disponible
