Title: Self-Stabilizing Disconnected Components Detection and Rooted Shortest-Path Tree Maintenance in Polynomial Steps,
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, 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.