@INPROCEEDINGS{6258020,
author={Datta, A.K. and Larmore, L.L. and Devismes, S. and Heurtefeux, K. and Rivierre, Y.},
booktitle={Distributed Computing Systems (ICDCS), 2012 IEEE 32nd International Conference on}, title={Competitive Self-Stabilizing k-Clustering},
year={2012},
month={june},
volume={},
number={},
pages={476 -485},
abstract={In this paper, we propose a silent self-stabilizing asynchronous distributed algorithm for constructing a kclustering of any connected network with unique IDs. Our algorithm stabilizes in O(n) rounds, using O(log n) space per process, where n is the number of processes. In the general case, our algorithm constructs O(n/k) k-clusters. If the network is a Unit Disk Graph (UDG), then our algorithm is 7.2552k+O(1)competitive, that is, the number of k-clusters constructed by the algorithm is at most 7.2552k + O(1) times the minimum possible number of k-clusters in any k-clustering of the same network. More generally, if the network is an Approximate Disk Graph (ADG) with approximation ratio #x03BB;, then our algorithm is 7.2552 #x03BB;2k + O( #x03BB;)-competitive. Our solution is based on the self-stabilizing construction of a data structure called the MIS Tree, a spanning tree of the network whose processes at even levels form a maximal independent set of the network. The MIS tree construction is the time bottleneck of our k-clustering algorithm, as it takes #x0398;(n) rounds in the worst case, while the rest of the algorithm takes O(D) rounds, where V is the diameter of the network. We would like to improve that time to be O(D), but we show that our distributed MIS tree construction is a P-complete problem.},
keywords={ADG;P-complete problem;UDG;approximate disk graph;approximation ratio;competitive self-stabilizing k-clustering;computational complexity;connected network;data structure;distributed MIS tree construction;k-clustering algorithm;maximal independent set;network diameter;network spanning tree;self-stabilizing asynchronous distributed algorithm;self-stabilizing construction;time bottleneck;unit disk graph;approximation theory;computational complexity;distributed algorithms;graph theory;pattern clustering;tree data structures;},
doi={10.1109/ICDCS.2012.72},
ISSN={1063-6927},}