Stéphane Devismes ; David Ilcinkas ; Colette Johnen - Self-Stabilizing Disconnected Components Detection and Rooted Shortest-Path Tree Maintenance in Polynomial Steps

dmtcs:3181 - Discrete Mathematics & Theoretical Computer Science, November 30, 2017, Vol. 19 no. 3 - https://doi.org/10.23638/DMTCS-19-3-14
Self-Stabilizing Disconnected Components Detection and Rooted Shortest-Path Tree Maintenance in Polynomial Steps

Authors: Stéphane Devismes ORCID-iD; David Ilcinkas ; Colette Johnen

    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.


    Volume: Vol. 19 no. 3
    Section: Distributed Computing and Networking
    Published on: November 30, 2017
    Accepted on: November 27, 2017
    Submitted on: August 22, 2017
    Keywords: Disconnected network,Routing algorithm,Shortest path,Distributed algorithm,Self-stabilization,Shortest-path tree,[INFO.INFO-NI] Computer Science [cs]/Networking and Internet Architecture [cs.NI]
    Fundings :
      Source : OpenAIRE Graph
    • Abstraction modulaire pour le calcul distribué; Funder: French National Research Agency (ANR); Code: ANR-16-CE40-0023
    • Auto-stabilisation et amélioration de la sûreté dans les environnements distribués évoluant dans le temps; Funder: French National Research Agency (ANR); Code: ANR-16-CE25-0009
    • Bouger et Calculer: Agents, Robots et Réseaux; Funder: French National Research Agency (ANR); Code: ANR-13-JS02-0002
    • Initiative d'excellence de l'Université de Bordeaux; Funder: French National Research Agency (ANR); Code: ANR-10-IDEX-0003

    Linked data

    Source : ScholeXplorer IsPartOf DOI 10.4230/lipics.opodis.2016
    • 10.4230/lipics.opodis.2016
    LIPIcs, Volume 70, OPODIS'16, Complete Volume
    Fatourou, Panagiota ; Pedone, Fernando ;

    Consultation statistics

    This page has been seen 570 times.
    This article's PDF has been downloaded 230 times.