Résumé | 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(maxi
max^3 n), where
maxi is the maximum weight of an edge,
max 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 3
max+D, where D is the hop-diameter of V_r. |