A Self-Stabilizing K-Clustering Algorithm Using an Arbitrary Metric

Eddy Caron (1) , Ajoy Datta (2) , Benjamin Depardon (1) , Lawrence Larmore (2)

1 LIP - Laboratoire de l'Informatique du Parallélisme
2 Department of Computer Science [Las Vegas]

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.

Nous présentons un algorithme asynchrone, distribué et auto-stabilisant pour construire un ensemble k-dominant, donnant lieu à un k-regroupement de nœuds ayant des identifiants uniques sur un graphe pondéré. 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, où n est la taille du réseau.Trouver un ensemble k-dominant minimal est un problème NP-difficile [1]. Nous présentons la première solution au problème du k-regroupement sur des graphes pondérés.

Mots clés: K-Clustering; Self-Stabilization; Weighted Graph

Mots clés: k-regroupement; Graphe pondéré; Auto-stabilisation

Domaines: Calcul parallèle, distribué et partagé [cs.DC]

Eddy Caron, Ajoy Datta, Benjamin Depardon, Lawrence Larmore. A Self-Stabilizing K-Clustering Algorithm Using an Arbitrary Metric. [Research Report] RR-7146, LIP RR-2008-31, INRIA, LIP. 2009, pp.41. ⟨inria-00440276⟩