Disconnected Components Detection and Rooted Shortest-Path Tree Maintenance in Networks

International audienceMany articles deal with the problem of maintaining a rooted shortest-path tree. However, after some edge deletions, some nodes can be disconnected from the connected component $V_r$ of some distinguished node~$r$. In this case, an additional objective is to ensure the detection of the disconnection bythe nodes that no longer belong to $V_r$. Without any assumption on the asynchronous model (\emph{unfair} daemon), with no knowledge of the network and within an anonymous network, we present a silent self-stabilizing algorithm solving this more demanding task and running in less than $2n+D$ rounds for a network of $n$ nodes and hop-diameter~$D$