Competitive self-stabilizing k-clustering

In this paper, we give a silent self-stabilizing algorithm for constructing a k  -clustering of any asynchronous connected network with unique IDs. Our algorithm stabilizes in O(n)O(n) rounds, using O(log⁡k+log⁡n)O(log⁡k+log⁡n) space per process, where n   is the number of processes. In the general case, our algorithm constructs O(nk)k  -clusters. If the network is a Unit Disk Graph (UDG), then our algorithm is 7.2552k+O(1)7.2552k+O(1)-competitive, that is, the number of k  -clusters constructed by the algorithm is at most 7.2552k+O(1)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 Quasi-Unit Disk Graph (QUDG) with approximation ratio λ  , then our algorithm is 7.2552λ2k+O(λ)7.2552λ2k+O(λ)-competitive. In case of tree networks, our algorithm computes a k-clustering with the minimum number of clusters. Our solution is based on the self-stabilizing construction of a data structure called an 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 we use (called LFMIS) is the time bottleneck of our k  -clustering algorithm, as it takes Θ(n)Θ(n) rounds in the worst case, while the rest of the algorithm takes O(D)O(D) rounds, where DD is the diameter of the network. We would like to improve that time to be O(D)O(D), but we show that our distributed MIS tree construction is a PP-complete problem.