Paper Info
Title
Silent self-stabilizing scheme for spanning-tree-like constructions.
Abstract
In this paper, we propose a general scheme, called Algorithm STlC, to compute spanning-tree-like data structures on arbitrary networks. STlC is self-stabilizing and silent and, despite its generality, is also efficient. It is written in the locally shared memory model with composite atomicity assuming the distributed unfair daemon, the weakest scheduling assumption of the model. Its stabilization time is in O(n(maxCC)) rounds, where n(maxCC) is the maximum number of processes in a connected component. We also exhibit polynomial upper bounds on its stabilization time in steps and process moves holding for large classes of instantiations of Algorithm STlC. We illustrate the versatility of our approach by proposing several such instantiations that efficiently solve classical problems such as leader election, as well as, unconstrained and shortest-path spanning tree constructions.
Year
DOI
Venue
2019
10.1145/3288599.3288607
ICDCN '19: PROCEEDINGS OF THE 2019 INTERNATIONAL CONFERENCE ON DISTRIBUTED COMPUTING AND NETWORKING
Keywords
Field
DocType
distributed algorithms,self-stabilization,spanning tree,leader election,spanning forest
Leader election,Atomicity,Data structure,Polynomial,Computer science,Theoretical computer science,Self-stabilization,Distributed algorithm,Spanning tree,Connected component,Distributed computing
Conference
Citations 
PageRank 
References 
0
0.34
21
Authors
3
Name
Order
Citations
PageRank
Stéphane Devismes119225.74
David Ilcinkas264834.44
Colette Johnen336431.21