Geodesic
Self-Stabilizing Disconnected Components Detection and Rooted Shortest-Path Tree Maintenance in Polynomial Steps
Discrete mathematics & theoretical computer science, Tome 19 (2017-2018) no. 3.

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2017_19_3_a13,
     author = {Devismes, St\'ephane and Ilcinkas, David and Johnen, Colette},
     title = {Self-Stabilizing {Disconnected} {Components} {Detection} and {Rooted} {Shortest-Path} {Tree} {Maintenance} in {Polynomial} {Steps}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {19},
     number = {3},
     year = {2017-2018},
     doi = {10.23638/DMTCS-19-3-14},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-3-14/}
}
TY  - JOUR
AU  - Devismes, Stéphane
AU  - Ilcinkas, David
AU  - Johnen, Colette
TI  - Self-Stabilizing Disconnected Components Detection and Rooted Shortest-Path Tree Maintenance in Polynomial Steps
JO  - Discrete mathematics & theoretical computer science
PY  - 2017-2018
VL  - 19
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-3-14/
DO  - 10.23638/DMTCS-19-3-14
LA  - en
ID  - DMTCS_2017_19_3_a13
ER  - 
%0 Journal Article
%A Devismes, Stéphane
%A Ilcinkas, David
%A Johnen, Colette
%T Self-Stabilizing Disconnected Components Detection and Rooted Shortest-Path Tree Maintenance in Polynomial Steps
%J Discrete mathematics & theoretical computer science
%D 2017-2018
%V 19
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-3-14/
%R 10.23638/DMTCS-19-3-14
%G en
%F DMTCS_2017_19_3_a13
Devismes, Stéphane; Ilcinkas, David; Johnen, Colette. Self-Stabilizing Disconnected Components Detection and Rooted Shortest-Path Tree Maintenance in Polynomial Steps. Discrete mathematics & theoretical computer science, Tome 19 (2017-2018) no. 3. doi : 10.23638/DMTCS-19-3-14. http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-3-14/

Cité par Sources :