Competitive self-stabilizing k-clustering

• Published in: Theoretical computer science 2016-05, Vol.626, p.110-133
• Main Authors: Datta, Ajoy K., Devismes, Stéphane, Heurtefeux, Karel, Larmore, Lawrence L., Rivierre, Yvan
• Format: Article
• Language: English
• Subjects: [formula omitted]-Completeness; Algorithms; Approximation; Competitiveness; Construction; Disks; Graphs; k-Clustering; Mathematical analysis; Maximal independent set; MIS tree; Networks; Self-stabilization; Trees
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/j.tcs.2016.02.010

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) rounds, using 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)-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 Quasi-Unit Disk Graph (QUDG) with approximation ratio λ, then our algorithm is 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) rounds in the worst case, while the rest of the algorithm takes O(D) rounds, where D 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.