World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

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

    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. Y. Sudo, A. K. Datta, L. L. Larmore and T. Masuzawa, 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. E. Korach, D. Rotem and N. Santoro, Distributed algorithms for finding centers and medians in networks, ACM Trans. Program. Lang. Syst. 6(3) :380–401, 1984. Crossref, ISIGoogle Scholar
    • 3. E. W. Dijkstra, Self stabilizing systems in spite of distributed control, Communications of the Association of Computing Machinery 17 :643–644, 1974. Crossref, ISIGoogle Scholar
    • 4. S. C. Bruell, S. Ghosh, M. H. Karaata and S. V. Pemmaraju, Self-stabilizing algorithms for finding centers and medians of trees, SIAM J. Comput. 29(2) :600–614, 1999. Crossref, ISIGoogle Scholar
    • 5. A. K. Datta and L. L. Larmore, 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. A. K. Datta, L. L. Larmore and T. Masuzawa, 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. V. Chepoi, T. Fevat, E. Godard and Y. Vaxès, A self-stabilizing algorithm for the median problem in partial rectangular grids and their relatives, Algorithmica 62(1–2) :146–168, 2012. Crossref, ISIGoogle Scholar
    • 8. F. R. Moore and G. G. Langdon, A generalized firing squad problem, Information and Control 12(3) :212–220, 1968. CrossrefGoogle Scholar
    • 9. A. Bui, A. K. Datta, F. Petit and V. Villain, Snap-stabilizing PIF in tree networks, Distributed Computing 20 :3–19, 2007. ISIGoogle Scholar
    • 10. D. Baba, T. Izumi, F. Ooshita, H. Kakugawa and T. Masuzawa, 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. K. Altisen and S. Devismes, On probabilistic snap-stabilization, Theoretical Computer Science 688 :49–76, 2017. Crossref, ISIGoogle Scholar