1. Optimized Silent Self-Stabilizing Scheme for Tree-Based Constructions.
- Author
-
Devismes, Stéphane, Ilcinkas, David, and Johnen, Colette
- Subjects
SPANNING trees ,BOTTLENECKS (Manufacturing) ,DATA structures ,DISTRIBUTED algorithms - Abstract
We propose a general scheme to compute tree-based data structures on arbitrary networks. This scheme is self-stabilizing, silent, and despite its generality, 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 at most 4 n maxCC rounds, where n maxCC is the maximum number of processes in any connected component of the network. We illustrate the versatility and efficiency of our approach by proposing several instantiations solving classical spanning tree problems such as DFS, BFS, shortest-path, or unconstrained spanning tree/forest constructions, as well as other fundamental problems like leader election or finding maximum-bottleneck-bandwidth paths. We also exhibit polynomial upper bounds on its stabilization time in steps and process moves, holding for a large class of instantiations. In several cases, the polynomial step and move complexities we obtain for those instantiations match the best known complexities of existing algorithms, despite the latter being dedicated to particular problems. Furthermore, a significant set of instantiations of our scheme requires only bounded memory space per process. This set includes, but is not limited to, DFS, BFS, and shortest-path spanning tree constructions. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF