Document Open Access Logo

Self-Stabilizing Disconnected Components Detection and Rooted Shortest-Path Tree Maintenance in Polynomial Steps

Authors Stéphane Devismes, David Ilcinkas, Colette Johnen

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2016.10.pdf
  • Filesize: 0.63 MB
  • 16 pages

Document Identifiers

Author Details

Stéphane Devismes
David Ilcinkas
Colette Johnen

Cite As Get BibTex

Stéphane Devismes, David Ilcinkas, and Colette Johnen. Self-Stabilizing Disconnected Components Detection and Rooted Shortest-Path Tree Maintenance in Polynomial Steps. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.OPODIS.2016.10

Abstract

We deal with the problem of maintaining a shortest-path tree rooted at some process r in a network that may be disconnected after topological changes. The goal is then to maintain a shortest-path tree rooted at r in its connected component, V_r, and make all processes of other components detecting that r is not part of their connected component. We propose, in the composite atomicity model, a silent self-stabilizing algorithm for this problem working in semi-anonymous networks under the distributed unfair daemon (the most general daemon) without requiring any a priori knowledge about global parameters of the network. This is the first algorithm for this problem that is proven to achieve a polynomial stabilization time in steps. Namely, we exhibit a bound in O(W_{max} * n_{maxCC}^3 * n), where W_{max} is the maximum weight of an edge, n_{maxCC} is the maximum number of non-root processes in a connected component, and n is the number of processes. The stabilization time in rounds is at most 3n_{maxCC} + D, where D is the hop-diameter of V_r.

Subject Classification

Keywords
  • distributed algorithm
  • self-stabilization
  • routing algorithm
  • shortest path
  • disconnected network
  • shortest-path tree

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Karine Altisen, Alain Cournier, Stéphane Devismes, Anaïs Durand, and Franck Petit. Self-stabilizing leader election in polynomial steps. Information and Computation, special issue of SSS 2014, 2016. To appear. Google Scholar
  2. A. Arora, M. G. Gouda, and T. Herman. Composite routing protocols. In the 2nd IEEE Symposium on Parallel and Distributed Processing (SPDP'90), pages 70-78, 1990. Google Scholar
  3. Richard Bellman. On a routing problem. Quart. Appl. Math., 16:87-90, 1958. Google Scholar
  4. Lélia Blin, Alain Cournier, and Vincent Villain. An improved snap-stabilizing PIF algorithm. In Shing-Tsaan Huang and Ted Herman, editors, Self-Stabilizing Systems, 6th International Symposium, SSS 2003, volume 2704 of Lecture Notes in Computer Science, pages 199-214, San Francisco, CA, USA, June 24-25 2003. Springer. Google Scholar
  5. Fabienne Carrier, Ajoy Kumar Datta, Stéphane Devismes, Lawrence L. Larmore, and Yvan Rivierre. Self-stabilizing (f, g)-alliances with safe convergence. J. Parallel Distrib. Comput., 81-82:11-23, 2015. URL: http://dx.doi.org/10.1016/j.jpdc.2015.02.001.
  6. Srinivasan Chandrasekar and Pradip K Srimani. A self-stabilizing distributed algorithm for all-pairs shortest path problem. Parallel Algorithms and Applications, 4(1-2):125-137, 1994. Google Scholar
  7. Ernest J. H. Chang. Echo Algorithms: Depth Parallel Operations on General Graphs. IEEE Trans. Software Eng., 8(4):391-401, 1982. Google Scholar
  8. N. S. Chen, H. P. Yu, and S. T. Huang. A self-stabilizing algorithm for constructing spanning trees. Information Processing Letters, 39:147-151, 1991. Google Scholar
  9. J. A. Cobb and M. G. Gouda. Stabilization of general loop-free routing. Journal of Parallel and Distributed Computing, 62(5):922-944, 2002. Google Scholar
  10. Alain Cournier, Stéphane Devismes, and Vincent Villain. Light enabling snap-stabilization of fundamental protocols. ACM Transactions on Autonomous and Adaptive Systems, 4(1), 2009. Google Scholar
  11. Alain Cournier, Stephane Rovedakis, and Vincent Villain. The first fully polynomial stabilizing algorithm for BFS tree construction. In the 15th International Conference on Principles of Distributed Systems (OPODIS'11), Springer LNCS 7109, pages 159-174, 2011. Google Scholar
  12. Ajoy K. Datta, Lawrence L. Larmore, and Priyanka Vemula. An o(n)-time self-stabilizing leader election algorithm. jpdc, 71(11):1532-1544, 2011. Google Scholar
  13. Ajoy Kumar Datta, Stéphane Devismes, and Lawrence L. Larmore. Brief announcement: Self-stabilizing silent disjunction in an anonymous network. In the 14th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS'12), Springer LNCS 7596, pages 46-48, 2012. Google Scholar
  14. Ajoy Kumar Datta, Lawrence L. Larmore, and Priyanka Vemula. Self-stabilizing leader election in optimal space under an arbitrary scheduler. Theoretical Computer Science, 412(40):5541-5561, 2011. Google Scholar
  15. Stéphane Devismes and Colette Johnen. Silent self-stabilizing BFStree algorithms revisited. Journal of Parallel and Distributed Computing, 97:11-23, 2016. URL: http://dx.doi.org/10.1016/j.jpdc.2016.06.003.
  16. Edsger W. Dijkstra. Self-stabilizing Systems in Spite of Distributed Control. Commun. ACM, 17(11):643-644, 1974. Google Scholar
  17. S. Dolev, A. Israeli, and S. Moran. Self-stabilization of dynamic systems assuming only Read/Write atomicity. Distributed Computing, 7(1):3-16, 1993. Google Scholar
  18. Shlomi Dolev. Self-stabilization. MIT Press, March 2000. Google Scholar
  19. Shlomi Dolev, Mohamed G. Gouda, and Marco Schneider. Memory requirements for silent stabilization. Acta Informatica, 36(6):447-462, 1999. Google Scholar
  20. Lester R. Ford Jr. Network flow theory, August 1956. Paper P-923, RAND Corporation, Santa Monica, California, USA. Google Scholar
  21. Christian Glacet, Nicolas Hanusse, David Ilcinkas, and Colette Johnen. Disconnected components detection and rooted shortest-path tree maintenance in networks. In the 16th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS'14), Springer LNCS 8736, pages 120-134, 2014. Google Scholar
  22. Christian Glacet, Nicolas Hanusse, David Ilcinkas, and Colette Johnen. Disconnected components detection and rooted shortest-path tree maintenance in networks - extended version. Technical report, LaBRI, CNRS UMR 5800, 2016. URL: https://hal.archives-ouvertes.fr/hal-01352245.
  23. Shing-Tsaan Huang and Nian-Shing Chen. A self-stabilizing algorithm for constructing breadth-first trees. Information Processing Letters, 41(2):109-117, 1992. Google Scholar
  24. Tetz C. Huang. A self-stabilizing algorithm for the shortest path problem assuming the distributed demon. Computers &Mathematics with Applications, 50(5–6):671-681, 2005. Google Scholar
  25. Tetz C. Huang and Ji-Cherng Lin. A self-stabilizing algorithm for the shortest path problem in a distributed system. Computers &Mathematics with Applications, 43(1):103-109, 2002. Google Scholar
  26. C. Johnen and S. Tixeuil. Route preserving stabilization. In the 6th International Symposium on Self-stabilizing System (SSS'03), Springer LNCS 2704, pages 184-198, 2003. Google Scholar
  27. Alberto Leon-Garcia and Indra Widjaja. Communication Networks. McGraw-Hill, Inc., New York, NY, USA, 2 edition, 2004. Google Scholar
  28. Adrian Segall. Distributed Network Protocols. IEEE Transactions on Information Theory, 29(1):23-34, 1983. Google Scholar
  29. M. Sloman and J. Kramer. Distributed systems and computer networks. Prentice Hall, 1987. Google Scholar
  30. G. Tel. Introduction to distributed algorithms. Cambridge University Press, Cambridge, UK, Second edition 2001. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact