A Self-Stabilizing K-clustering algorithm for weighted graphs - Archive ouverte HAL Access content directly
Journal Articles Journal of Parallel and Distributed Computing Year : 2010

A Self-Stabilizing K-clustering algorithm for weighted graphs

(1) , (2) , (1) , (2)
1
2

Abstract

Mobile ad hoc networks as well as grid platforms are distributed, changing and error prone environments. Communication costs within such infrastructure can be improved, or at least bounded, by using k-clustering. A k-clustering of a graph, is a partition of the nodes into disjoint sets, called clusters, in which every node is distance at most k from a designated node in its cluster, called the clusterhead. A self-stabilizing asynchronous distributed algorithm is given for constructing a k-clustering of a connected network of processes with unique IDs and weighted edges. The algorithm is comparison-based, takes O(nk) time, and uses O(log n + log k) space per process, where n is the size of the network. This is the first distributed solution to the k-clustering problem on weighted graphs.
Les réseaux mobiles ad hoc ainsi que les plate-formes de grille sont des environements distribués et sujets à de nombreuses erreurs. Les coûts de communication au sein de ses 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, nommés grappes ou clusters, dans lesquels chaque noeud est à une distance au plus k d'un noeud élu au sein du cluster, appelé clusterhead. Nous présentons un algorithme asynchrone, distribué et auto-stabilisant pour construire un ensemble k-regroupement d'un réseau de noeuds ayant des identifiants uniques, et connectés par des arêtes pondérées. L'algorithme se base sur les comparaisons des 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. Nous présentons la première solution au problème du k-regroupement sur des graphes pondérés.
Not file

Dates and versions

hal-00758590 , version 1 (29-11-2012)

Identifiers

  • HAL Id : hal-00758590 , version 1

Cite

Eddy Caron, Ajoy K. Datta, Benjamin Depardon, Lawrence L. Larmore. A Self-Stabilizing K-clustering algorithm for weighted graphs. Journal of Parallel and Distributed Computing, 2010, 70 (11), pp.1159-1173. ⟨hal-00758590⟩
85 View
0 Download

Share

Gmail Facebook Twitter LinkedIn More