A Self-Stabilizing Minimal k-Grouping Algorithm

Document Type

Conference Proceeding

Publication Date

1-5-2017

Publication Title

Proceedings of the 18th International Conference on Distributed Computing and Networking

First page number:

3

Abstract

We consider the minimal k-grouping problem: given a graph G = (V, E) and a constant k, partition G into subgraphs of diameter no greater than k, such that the union of any two subgraphs has diameter greater than k. We give a silent self-stabilizing asynchronous distributed algorithm for this problem in the composite atomicity model of computation, assuming the network has unique process identifiers. Our algorithm works under the weakly-fair daemon. The time complexity (i.e. the number of rounds to reach a legitimate configuration) of our algorithm is O (nD/k) where n is the number of processes in the network and D is the diameter of the network. The space complexity of each process is O((n + nfalse) log n) where nfalse is the number of false identifiers, i.e., identifiers that do not match the identifier of any process, but which are stored in the local memory of at least one process at the initial configuration. Our algorithm guarantees that the number of groups is at most 2n/k + 1 after convergence. We also give a novel composition technique to concatenate a silent algorithm repeatedly, which we call loop composition.

Language

english

Find It

UNLV article access

Share

COinS