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.

A SILENT SELF-STABILIZING ALGORITHM FOR FINDING CUT-NODES AND BRIDGES

    In this paper, we present a self-stabilizing algorithm for finding cut-nodes and bridges in arbitrary rooted networks with a low memory requirement (O(log(n)) bits per processor where n is the number of processors). Our algorithm is silent and must be composed with a silent self-stabilizing algorithm computing a Depth-First Search (DFS) Spanning Tree of the network. So, in the paper, we will prove that the composition of our algorithm with any silent self-stabilizing DFS algorithm is self-stabilizing. Finally, we will show that our algorithm needs O(n2) moves to reach a terminal configuration once the DFS spanning tree is computed. Note that this time complexity is equivalent to the best proposed solutions.

    References

    • E. W. Dijkstra, Communications of the Association of the Computing Machinery 17, 643 (1974). Crossref, ISIGoogle Scholar
    • K. Paton, Communications of the ACM 37, 468 (1971). Google Scholar
    • Robert E. Tarjan, SIAM J. Computing 1(2), (1972). Google Scholar
    • M. Ahuja and Y. Zhu. An efficient distributed algorithm for finding articulation points, bridges and biconnected components in asynchronous networks. In 9th Conference on Foundations of Software Technology and Theorical Computer Science, Banglore, India, pages 99-108. LNCS 405, 1989 . Google Scholar
    • J. Parkset al., Systems and Computers in Japan 22, 1 (1991). CrossrefGoogle Scholar
    • A. P. Spraque and K. H. Kulkarni, Information Processing Letters 42, 229 (1992). Crossref, ISIGoogle Scholar
    • M. Hakan Karaata, International Journal of Foundations of Computer Science 10(1), 33 (1999). Link, ISIGoogle Scholar
    • M. Hakan Karaata and P. Chaudhuri, Distributed Computing 12(1), 47 (1999). Crossref, ISIGoogle Scholar
    • P. Chaudhuri, Computing 62, 55 (1999). Crossref, ISIGoogle Scholar
    • P. Chaudhuri, Journal of Systems Architecture 45(14), 1249 (1999). Crossref, ISIGoogle Scholar
    • S. Dolev, A. Israeli and S. Moran, Distributed Computing 7, 3 (1993). Crossref, ISIGoogle Scholar
    • S. Dolev, A. Israeli and S. Moran, IEEE Transactions on Parallel and Distributed Systems 8(4), 424 (1997). Crossref, ISIGoogle Scholar
    • G.   Tel , Introduction to distributed algorithms ( Cambridge University Press , 1994 ) . CrossrefGoogle Scholar
    • T. Herman. Adaptivity through distributed convergence. PhD thesis, University of Texas at Austin, Departement of Computer Science, 1991 . Google Scholar
    • Z. Collin and S. Dolev, Information Processing Letters 49(6), 297 (1994). Crossref, ISIGoogle Scholar
    • Y. Afek and A. Bremler, Chicago Journal of Theoretical Computer Science  (1998). Google Scholar
    • B. Ducourthial and S. Tixeuil, Distributed Computing 14(3), 147 (2001). Crossref, ISIGoogle Scholar