Self-Stabilizing Disconnected Components Detection and Rooted Shortest-Path Tree Maintenance in Polynomial StepsReport as inadecuate




Self-Stabilizing Disconnected Components Detection and Rooted Shortest-Path Tree Maintenance in Polynomial Steps - Download this document for free, or read online. Document in PDF available to download.

1 SYNCHRONE VERIMAG - IMAG - VERIMAG 2 LaBRI - Laboratoire Bordelais de Recherche en Informatique

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, Vr, 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 3nmaxCC + D, where nmaxCC is the maximum number of non-root processes in a connected component and D is the hop-diameter of Vr.
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 OWmaxnmaxCC 3 n, where Wmax is the maximum weight of an edge and n is the number of processes.


Keywords : distributed algorithm self-stabilization routing algorithm shortest path disconnected network shortest-path tree





Author: Stéphane Devismes - David Ilcinkas - Colette Johnen -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents