Constant Space Self-stabilizing Center Finding Algorithms in Chains and Trees

Document Type

Article

Publication Date

3-29-2018

Publication Title

Parallel Processing Letters

Volume

28

Issue

1

First page number:

1

Last page number:

15

Abstract

Self-stabilizing, but non-silent, distributed algorithms, for center finding in chain and tree networks are presented in the link register model. We assume that there exists a designated root in a chain and a tree. Under this assumption, both algorithms find the unique center or one of the two centers of the network within O(diam) rounds under the unfair daemon, where diam is the diameter of the network. Both algorithms use constant space, both per process and per link register. The basic strategy of the chain algorithm is based on two synchronized waves of different speeds; one wave is three times faster than the other. The tree algorithm uses the fact that a center of the longest path in the tree is also a center of the tree itself. It first finds one of the longest paths in the tree, then finds the unique center or one of the two centers of the path using the chain algorithm.

Keywords

Center finding; Chain networks; Self-stabilization; Tree networks; Unfair daemon

Disciplines

Theory and Algorithms

Language

English

Find It

UNLV article access

Find in your library

Share

COinS