Snap-stabilizing tasks in anonymous networks
From MaRDI portal
Publication:5918192
DOI10.1007/978-3-319-49259-9_14zbMATH Open1425.68032arXiv2203.06012OpenAlexW2548292593MaRDI QIDQ5918192
Publication date: 22 November 2019
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Abstract: We consider snap-stabilizing algorithms in anonymous networks. Self-stabilizing algorithms are well known fault tolerant algorithms : a self-stabilizing algorithm will eventually recover from arbitrary transient faults. On the other hand, an algorithm is snap-stabilizing if it can withstand arbitrary initial values and immediately satisfy its safety requirement. It is a subset of self-stabilizing algorithms. Distributed tasks that are solvable with self-stabilizing algorithms in anonymous networks have already been characterized by Boldi and Vigna in [BV02b]. In this paper, we show how the more demanding snap-stabilizing algorithms can be handled with standard tools for (not stabilizing) algorithms in anonymous networks. We give a characterization of which tasks are solvable by snap-stabilizing algorithms in anonymous networks. We also present a snap-stabilizing version of Mazurkiewicz' enumeration algorithm. This work exposes, from a task-equivalence point of view, the complete correspondence in anonymous networks between self or snap-stabilizing tasks and distributed tasks with various termination detection requirements.
Full work available at URL: https://arxiv.org/abs/2203.06012
Distributed systems (68M14) Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed algorithms (68W15)
Related Items (2)
Snap-stabilizing tasks in anonymous networks ⋮ Optimized silent self-stabilizing scheme for tree-based constructions
This page was built for publication: Snap-stabilizing tasks in anonymous networks
