Self-stabilizing clustering of tree networks

In this paper, we present a self-stabilizing algorithm for finding clustering of tree networks on a distributed model of computation. Clustering is defined as the covering of the nodes of a network by subtrees such that the intersection of any two subtrees is at most a single node and the difference between the sizes of the largest and the smallest clusters are minimal. The proposed algorithm evenly partitions the network into nearly the same size clusters and places resources and services for each cluster at its clusterhead to minimize the cost of sharing resources and using the services. Due to being self-stabilizing, the algorithm can withstand transient faults and does not require initialization. The paper includes a correctness proof of the algorithm. It concludes with remarks on issues such as open and related problems and the application areas of the algorithm.