Evènement pour le groupe Algorithmique Distribuée

Date 2017-03-20  14:00-15:00
TitreSelf-Stabilizing Disconnected Components Detection and Rooted Shortest-Path Tree Maintenance in Polynomial Steps 
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. 
OrateurDavid Ilcinkas 

Aucun document lié à cet événement.

Retour à l'index