Colette Johnen (LaBRI)
Title: From Static Stabilization to Dynamic Stabilization in case of bounded recurrent edges
Abstract:
We consider the problem of the Dynamic Simulation, which consists in the design of a transformer that simulates distributed algorithms in a dynamic environment modeled by a dynamic graph. We consider dynamic graphs with a fixed topology, meaning that each existing edge appears infinitely often.
We introduce a self-stabilizing transformer adapted to graphs where every edge appears at least once during τ consecutive synchronous rounds.
Our transformer is minimal in terms of hypotheses in the following sense: solving the Dynamic Simulation Problem in graphs with recurring edges either requires the knowledge of either a bound on the edge recurrency (i.e. τ
), or the knowledge on number of edges.
Finally, we introduce the notion of time-bounded stabilization corresponding to pseudo-stabilizing algorithms for which an upper bound on the convergence time depending only of the network's topology.
joint work with Gabriel Le Bouder