"A Self-stabilizing O(n)-round k-clustering Algorithm" by Ajoy K. Datta, Stephane Devismes et al.
 

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.

File Format

pdf

File Size

327 kb

Language

english

UNLV article access

Plum Print visual indicator of research metrics
PlumX Metrics
  • Citations
    • Citation Indexes: 23
  • Usage
    • Abstract Views: 3
  • Captures
    • Readers: 6
see details

Share

COinS