Stabilizing ring clustering

Mehmet Hakan Karaata

doi:10.1016/j.sysarc.2004.02.002

Return

Stabilizing ring clustering

2004-10-01

PRE

Mehmet Hakan Karaata *

DOI：10.1016/j.sysarc.2004.02.002

Original

Original request for help

Save

Abstract

En 中文

In this paper, we first present simple stabilizing algorithms for finding clustering of ring networks on a distributed model of computation. Clustering is defined as partitioning of nodes of a network into non-overlapping sets of nodes based on certain criteria. Our criterion for partitioning the network is that the difference between the sizes of the largest cluster and the smallest cluster is minimal. We first present a uniform algorithm that evenly partitions the network into nearly the same size clusters. The clusters may continuously move in one direction while maintaining the difference of at most one between the size of the largest and the size of the smallest cluster. Then, we present a non-uniform self-stabilizing algorithm for the same problem that terminates after O(n(2)) moves. When resources are placed at cluster boundaries (or centers), the cost of sharing resources is minimized. The algorithms can withstand transient faults and do not require initialization. In addition, when the ring size changes, the proposed algorithms automatically identify the clusterings of the new ring. The paper includes correctness proofs of the algorithms. It concludes with remarks on issues such as open and related problems, and the application areas of the algorithm. (C) 2004 Elsevier B.V. All rights reserved.

Keywords:

clustering

distributed systems

fault-tolerance

p-centers

self-stabilization

ring

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.