{"docId":4116,"paperId":3181,"url":"https:\/\/dmtcs.episciences.org\/3181","doi":"10.23638\/DMTCS-19-3-14","journalName":"Discrete Mathematics & Theoretical Computer Science","issn":"","eissn":"1365-8050","volume":[{"vid":312,"name":"Vol. 19 no. 3"}],"section":[{"sid":8,"title":"Distributed Computing and Networking","description":[]}],"repositoryName":"Hal","repositoryIdentifier":"hal-01485652","repositoryVersion":4,"repositoryLink":"https:\/\/hal.archives-ouvertes.fr\/hal-01485652v4","dateSubmitted":"2017-08-22 14:08:38","dateAccepted":"2017-11-30 17:04:45","datePublished":"2017-11-30 17:05:03","titles":{"en":"Self-Stabilizing Disconnected Components Detection and Rooted Shortest-Path Tree Maintenance in Polynomial Steps"},"authors":["Devismes, St\u00e9phane","Ilcinkas, David","Johnen, Colette"],"abstracts":{"en":"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, where edges have strictly positive weights. This algorithm does not require any a priori knowledge about global parameters of the network. We prove its correctness assuming the distributed unfair daemon, the most general daemon. Its stabilization time in rounds is at most 3nmax+D, where nmax is the maximum number of non-root processes in a connected component and D is the hop-diameter of V_r. Furthermore, if we additionally assume that edge weights are positive integers, then it stabilizes in a polynomial number of steps: namely, we exhibit a bound in O(maxi nmax^3 n), where maxi is the maximum weight of an edge and n is the number of processes."},"keywords":[["Disconnected network"],["Routing algorithm"],["Shortest path"],["Distributed algorithm"],["Self-stabilization"],["Shortest-path tree"],"[INFO.INFO-NI] Computer Science [cs]\/Networking and Internet Architecture [cs.NI]"]}