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.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/hal-00758594
Contributor : Eddy Caron <>
Submitted on : Thursday, November 29, 2012 - 2:41:54 AM
Last modification on : Friday, April 20, 2018 - 3:44:24 PM

Identifiers

  • 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. ⟨hal-00758594⟩

Share

Metrics

Record views

122