A Self-Stabilizing O(n)-Round k-Clustering Algorithm

Abstract

Given an arbitrary network G of processes with unique IDs and no designated leader, and given a k-dominating set I C G, we propose a silent self-stabilizing distributed algorithm that computes a subset D of I which is a minimal k-dominating set of G. Using D as the set of cluster-heads, a partition of G into clusters, each of radius k, follows. The algorithm is comparison-based, requires O(log n) space per process, converges in O(n) rounds and O(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ) steps, where n is the size of the network, and works under an unfair scheduler.