Titre :	Un nouvel algorithme auto- stabilisant pour le calcul d'un ensemble dominant à ditance k
Type de document :	texte imprimé
Auteurs :	Battaa, Mohamed Sofiane, Auteur ; Guellati, Nabil, Directeur de thèse
Editeur :	Setif:UFA
Année de publication :	2018
Importance :	1 vol (55 f .)
Format :	29 cm
Langues :	Français (fre) Langues originales : Français (fre)
Catégories :	Thèses & Mémoires:Informatique
Mots-clés :	Auto-stabilisation Systèmes distribués Algorithmes distribués
Index. décimale :	004 Informatique
Résumé :	Résumé L’auto stabilisation est une technique qui permet la tolérance aux pannes transi- toires. Elle a été introduite par E. W. Dijkstra en 1974. Un système ou un algo- rithme distribué est dit auto stabilisant si à partir de n’importe quel état initial, il est capable de retrouver automatiquement un état correct au bout d’un temps fini. De nombreux problèmes étudiés dans les réseaux et les systèmes repartis peuvent être modélises par des graphes. Plusieurs recherches ont été menées dans ce do- maine et plusieurs algorithmes repartis de graphe ont été développés. Nous étudions dans ce travail, les algorithmes distribués auto stabilisants qui permettent le calcul d’ensembles dominants et indépendants dans un graphe. Nous présentons un nouvel algorithme distribué auto stabilisant qui permet le calcul d’un ensemble dominant à distance k (DKDS : distance-k dominating set ) dans un graphe arbitraire. Nous allons évaluer ses performances par simulation de son comportement dans un en- vironnement à grand échèle. Ensuite, nous allons effectuer une comparaison entre notre algorithme et d’autres algorithmes similaires dans la littérature et discuter les résultats obtenues. Notre algorithme peut être utilisé pour l’organisation des res- sources dans un système distribué et il est utile pour faire du clustering dans les réseaux (organisation des noeuds d’un réseau en groupes).
Note de contenu :	Table des matières Introduction générale 1 1 L’auto-stabilisation dans les Systèmes distribués 2 Introduction 2 Système distribué 2 Algorithme distribué 3 Les Types de pannes 5 La tolérance aux pannes 6 L’auto-stabilisation 6 Définition 6 Premier algorithme auto stabilisant 7 Les avantages et les inconvenants de l’auto stabilisation 10 Définitions formelles 10 Preuve d’auto stabilisation 11 Preuve de correction 11 Preuve de convergence 11 Complexité 12 Complexité en espace 12 Complexité en temps 12 Démons 13 Conclusion 13 2 Les algorithmes distribués auto stabilisants d’ensembles dominants et indépendants 15 Introduction 15 Usage des ensembles dominants et indépendants dans le clustering 15 Avantages du clustering 16 Définitions 17 État de l’art sur les algorithmes distribués auto-stabilisants d’en- sembles dominants et indépendants 19 Les algorithmes de Hedetniemi 20 Les algorithmes de Turau (MIS et MDS) 22 L’algorithme de Chiu (MDS) 25 L’algorithme de Goddard (MIS) 27 L’algorithme de Goddard (MDS) 28 L’algorithme de Neggazi (ISDS) 30 L’algorithme de Srimani (MTDS) 31 L’algorithme de Huang (MKDS /K=2) 33 L’algorithme de Lin (MKDS /K=2) 34 2.5 Récapitulation 36 2.6 conclusion 37 3.Un vouvel algorithme distribué auto-stabilisant (DKDS) 38 3.1 Introduction 38 3.2 Défintion 38 3.3 Usage des ensemble DKDS 40 3.4 Hipothèse de notre algorithme 41 3.5 Désctiption de l'algorithme 41 3.6 La preuve de l'algorithme 45 3.6.1 preuve de convergence 45 3.7 Analyse de complexité 47 3.8 Simulation 49 3.9 Interface de l'application 51 3.10 Conclusion 52 Conclusion générale 53 Bibliographie 54
Côte titre :	MAI/0213
En ligne :	https://drive.google.com/file/d/1tP5i4_CZLN-Uh8SLdSmb0oQffEw0vZkJ/view?usp=shari [...]
Format de la ressource électronique :	pdf

Un nouvel algorithme auto- stabilisant pour le calcul d'un ensemble dominant à ditance k [texte imprimé] / Battaa, Mohamed Sofiane, Auteur ; Guellati, Nabil, Directeur de thèse . - [S.l.] : Setif:UFA, 2018 . - 1 vol (55 f .) ; 29 cm.
Langues : Français (fre) Langues originales : Français (fre)

Catégories :	Thèses & Mémoires:Informatique
Mots-clés :	Auto-stabilisation Systèmes distribués Algorithmes distribués
Index. décimale :	004 Informatique
Résumé :	Résumé L’auto stabilisation est une technique qui permet la tolérance aux pannes transi- toires. Elle a été introduite par E. W. Dijkstra en 1974. Un système ou un algo- rithme distribué est dit auto stabilisant si à partir de n’importe quel état initial, il est capable de retrouver automatiquement un état correct au bout d’un temps fini. De nombreux problèmes étudiés dans les réseaux et les systèmes repartis peuvent être modélises par des graphes. Plusieurs recherches ont été menées dans ce do- maine et plusieurs algorithmes repartis de graphe ont été développés. Nous étudions dans ce travail, les algorithmes distribués auto stabilisants qui permettent le calcul d’ensembles dominants et indépendants dans un graphe. Nous présentons un nouvel algorithme distribué auto stabilisant qui permet le calcul d’un ensemble dominant à distance k (DKDS : distance-k dominating set ) dans un graphe arbitraire. Nous allons évaluer ses performances par simulation de son comportement dans un en- vironnement à grand échèle. Ensuite, nous allons effectuer une comparaison entre notre algorithme et d’autres algorithmes similaires dans la littérature et discuter les résultats obtenues. Notre algorithme peut être utilisé pour l’organisation des res- sources dans un système distribué et il est utile pour faire du clustering dans les réseaux (organisation des noeuds d’un réseau en groupes).
Note de contenu :	Table des matières Introduction générale 1 1 L’auto-stabilisation dans les Systèmes distribués 2 Introduction 2 Système distribué 2 Algorithme distribué 3 Les Types de pannes 5 La tolérance aux pannes 6 L’auto-stabilisation 6 Définition 6 Premier algorithme auto stabilisant 7 Les avantages et les inconvenants de l’auto stabilisation 10 Définitions formelles 10 Preuve d’auto stabilisation 11 Preuve de correction 11 Preuve de convergence 11 Complexité 12 Complexité en espace 12 Complexité en temps 12 Démons 13 Conclusion 13 2 Les algorithmes distribués auto stabilisants d’ensembles dominants et indépendants 15 Introduction 15 Usage des ensembles dominants et indépendants dans le clustering 15 Avantages du clustering 16 Définitions 17 État de l’art sur les algorithmes distribués auto-stabilisants d’en- sembles dominants et indépendants 19 Les algorithmes de Hedetniemi 20 Les algorithmes de Turau (MIS et MDS) 22 L’algorithme de Chiu (MDS) 25 L’algorithme de Goddard (MIS) 27 L’algorithme de Goddard (MDS) 28 L’algorithme de Neggazi (ISDS) 30 L’algorithme de Srimani (MTDS) 31 L’algorithme de Huang (MKDS /K=2) 33 L’algorithme de Lin (MKDS /K=2) 34 2.5 Récapitulation 36 2.6 conclusion 37 3.Un vouvel algorithme distribué auto-stabilisant (DKDS) 38 3.1 Introduction 38 3.2 Défintion 38 3.3 Usage des ensemble DKDS 40 3.4 Hipothèse de notre algorithme 41 3.5 Désctiption de l'algorithme 41 3.6 La preuve de l'algorithme 45 3.6.1 preuve de convergence 45 3.7 Analyse de complexité 47 3.8 Simulation 49 3.9 Interface de l'application 51 3.10 Conclusion 52 Conclusion générale 53 Bibliographie 54
Côte titre :	MAI/0213
En ligne :	https://drive.google.com/file/d/1tP5i4_CZLN-Uh8SLdSmb0oQffEw0vZkJ/view?usp=shari [...]
Format de la ressource électronique :	pdf