A Self-stabilizing O(n)-round k-clustering Algorithm
Document Type
Conference Proceeding
Publication Date
1-1-2009
Publication Title
28th IEEE International Symposium on Reliable Distributed Systems
Volume
2009
First page number:
147
Last page number:
155
Abstract
Given an arbitrary network G of processes with unique IDs and no designated leader, and given a k-dominating set I ⊆ G, we propose a silent selfstabilizing distributed algorithm that computes a subset D of I which is a minimal k-dominating set of G. Using D as the set of clusterheads, 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(n2) steps, where n is the size of the network, and works under an unfair scheduler.
Language
english
Repository Citation
Datta, A. K.,
Devismes, S.,
Larmore, L. L.
(2009).
A Self-stabilizing O(n)-round k-clustering Algorithm.
28th IEEE International Symposium on Reliable Distributed Systems, 2009
147-155.
http://dx.doi.org/10.1109/SRDS.2009.13