An O(D)-Round Snap-stabilizing Termination Detection in Arbitrary Rooted Networks

Read full text Summarise with VIRAT
Authors: Karine Altisen, Alain Cournier, Geoffrey Defalque, Stéphane Devismes
Cited by: 0
References: 39

Summary

No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.

Summarise with VIRAT Free to try with your Science Catalogs account.

Abstract

In this paper, we investigate the question of (asymptotic) time optimality for snap-stabilizing wave algorithms. Snap-stabilization is a refinement of self-stabilization guaranteeing that after a period of transient faults, any system achieving it immediately resumes a correct behavior. We consider here the atomic-state model under the distributed weakly fair daemon in the context of rooted connected networks. In these settings, we propose to augment a silent BFS spanning tree construction with efficient snap-stabilizing termination detection. This approach yields an asynchronous snap-stabilizing wave algorithm that both constructs a BFS spanning tree and detects the termination of its construction in O(D) rounds and using O(log ∆ + log D) bits per process, where ∆ is the maximum degree of the network and D is any upper bound on D. As a result, and to the best of our knowledge, we obtain the first asynchronous asymptotically round-optimal snap-stabilizing wave algorithm of the literature. We then generalize our approach to augment any silent algorithm with snap-stabilizing termination detection. This leads to a snap-stabilizing wave algorithm that both executes the silent task and detects its termination in O(F + D) rounds, where F is the stabilization time of the input silent algorithm; thereby incurring an asymptotically optimal additive overhead of O(D) rounds. The memory overhead also remains low, namely O(log ∆ + log D) additional bits per process.

Fields of Study & Subjects

Distributed systems and fault tolerance Formal Methods in Verification Optimization and Search Problems

Publication details

Journal / source
HAL
Publication date
19 February 2026
Language
EN
Document type
Preprint