2026-08-16T15:14:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7079 2024-03-06T10:39:30Z ddc:004 open_access

Self-Stabilizing Disconnected Components Detection and Rooted Shortest-Path Tree Maintenance in Polynomial Steps Devismes, Stéphane Ilcinkas, David Johnen, Colette distributed algorithm self-stabilization routing algorithm shortest path disconnected network shortest-path tree 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Stéphane Devismes and David Ilcinkas and Colette Johnen 2017 Is Part Of LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2016.10 urn:nbn:de:0030-drops-70792 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.10 eng https://creativecommons.org/licenses/by/3.0/legalcode