Un algorithme auto-stabilisant pour le problème du k-partitionnement sur graphe pondéré

Benjamin Depardon 1
1 GRAAL - Algorithms and Scheduling for Distributed Heterogeneous Platforms
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Résumé : Les réseaux mobiles ad hoc ainsi que les plates-formes de grille sont des environnements distribués et sujets à de nombreuses erreurs. Les coûts de communication au sein de ces infrastructures peuvent être améliorés, ou tout au moins bornés par l'utilisation d'un k-regroupement. Un k-regroupement d'un graphe, est une partition des noeuds en ensembles disjoints, dans lesquels chaque noeud est à une distance au plus k d'un noeud élu au sein de l'ensemble. Nous présentons un algorithme asynchrone, distribué et auto-stabilisant pour construire un k-regroupement sur un graphe pondéré. L'algorithme se base sur des comparaisons entre les identifiants, il s'exécute en O(nk), et requiert O(log n + log k) d'espace mémoire par processus, où n est la taille du réseau.
Type de document :
Communication dans un congrès
RenPar'19, 19e Rencontres Francophones du Parallélisme, Sep 2009, Toulouse, France. 2009
Liste complète des métadonnées

https://hal.inria.fr/hal-00758594
Contributeur : Eddy Caron <>
Soumis le : jeudi 29 novembre 2012 - 02:41:54
Dernière modification le : mercredi 11 avril 2018 - 01:55:42

Identifiants

  • HAL Id : hal-00758594, version 1

Collections

Citation

Benjamin Depardon. Un algorithme auto-stabilisant pour le problème du k-partitionnement sur graphe pondéré. RenPar'19, 19e Rencontres Francophones du Parallélisme, Sep 2009, Toulouse, France. 2009. 〈hal-00758594〉

Partager

Métriques

Consultations de la notice

104