Constant Space Self-stabilizing Center Finding Algorithms in Chains and Trees
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.
An earlier version of this paper appeared as a Brief Announcement in [1].
References
- 1. , Brief announcement: Reduced space self-stabilizing center finding algorithms in chains and trees, in Stabilization, Safety, and Security of Distributed Systems — 19th International Symposium, SSS 2017,
2017 (To Appear). Google Scholar - 2. , Distributed algorithms for finding centers and medians in networks, ACM Trans. Program. Lang. Syst. 6(3) :380–401, 1984. Crossref, ISI, Google Scholar
- 3. , Self stabilizing systems in spite of distributed control, Communications of the Association of Computing Machinery 17 :643–644, 1974. Crossref, ISI, Google Scholar
- 4. , Self-stabilizing algorithms for finding centers and medians of trees, SIAM J. Comput. 29(2) :600–614, 1999. Crossref, ISI, Google Scholar
- 5. , Leader election and centers and medians in tree networks, in Stabilization, Safety, and Security of Distributed Systems — 15th International Symposium, SSS 2013, pages 113–132, 2013. Google Scholar
- 6. , Constant space self-stabilizing center finding in anonymous tree networks, in Proceedings of the 2015 International Conference on Distributed Computing and Networking, ICDCN 2015, pages 38:1–38:10, 2015. Google Scholar
- 7. , A self-stabilizing algorithm for the median problem in partial rectangular grids and their relatives, Algorithmica 62(1–2) :146–168, 2012. Crossref, ISI, Google Scholar
- 8. , A generalized firing squad problem, Information and Control 12(3) :212–220, 1968. Crossref, Google Scholar
- 9. , Snap-stabilizing PIF in tree networks, Distributed Computing 20 :3–19, 2007. ISI, Google Scholar
- 10. , Space-optimal rendezvous of mobile agents in asynchronous trees, in International Colloquium on Structural Information and Communication Complexity, pages 86–100,
2010 . Google Scholar - 11. , On probabilistic snap-stabilization, Theoretical Computer Science 688 :49–76, 2017. Crossref, ISI, Google Scholar


