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

Author

Datta, Ajoy K. ; Devismes, Stéphane ; Larmore, Lawrence L.

Author_Institution

Sch. of Comput. Sci., Univ. of Nevada, Las Vegas, NV, USA

fYear

2009

fDate

27-30 Sept. 2009

Firstpage

147

Lastpage

155

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²) steps, where n is the size of the network, and works under an unfair scheduler.

Keywords

computational complexity; distributed algorithms; fault tolerant computing; graph theory; network theory (graphs); pattern clustering; scheduling; set theory; arbitrary distributed network; cluster-head set; distributed system fault tolerance; graph partitioning; minimal k-dominating set; silent self-stabilizing k-clustering distributed algorithm convergence; unfair scheduling; Algorithm design and analysis; Clustering algorithms; Computer networks; Computer science; Distributed algorithms; Distributed computing; Intrusion detection; Partitioning algorithms; Scheduling algorithm; USA Councils; K-clustering; K-dominating set; self-stabilization; silent; unfair scheduler;

fLanguage

English

Publisher

ieee

Conference_Titel

Reliable Distributed Systems, 2009. SRDS '09. 28th IEEE International Symposium on

Conference_Location

Niagara Falls, NY

ISSN

1060-9857

Print_ISBN

978-0-7695-3826-6

Type

conf

DOI

10.1109/SRDS.2009.13

Filename

5283347