| Article Id: |
 |
ensl-00440266, version 1 |
|
|
| Domaine: |
|
Computer Science/Distributed, Parallel, and Cluster Computing
|
|
|
| Titre: |
|
A Self-Stabilizing K-Clustering Algorithm Using an Arbitrary Metric (Revised Version of RR2008-31) |
|
|
| Auteur(s): |
|
Eddy Caron1, Ajoy Datta2, Benjamin Depardon1, Lawrence Larmore2 |
|
|
| Laboratoire: |
|
| 1: |
LIP - Laboratoire de l'Informatique du Parallélisme |
|
| 2: |
SCV - School of Computer Science [ Nevada - Las Vegas] |
|
|
|
| Résumé: |
|
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. |
|
|
|
Langue du texte
intégral: |
|
English |
|
|
| Mots-clés: |
|
K-Clustering – Self-Stabilization – Weighted Graph |
|
|
| Commentaire: |
|
32 pages |
|
|
| Référence interne: |
|
RRLIP2009-33 |
|
|
|
Export this paper
