Optimized silent self-stabilizing scheme for tree-based constructions

DOI10.1007/S00453-021-00878-9MaRDI QIDQ2072099zbMATH OpenOpenAlexFDO

Authors Stéphane Devismes, David Ilcinkas, Colette Johnen

Publication date 1 February 2022

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-021-00878-9

zbMATH Keywords

distributed algorithmsleader electionself-stabilizationspanning treespace complexityspanning foreststabilization time

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed algorithms (68W15) Graph theory (05Cxx)

Recommendations

• A new polynomial silent stabilizing spanning-tree construction algorithm
• Time Optimal Asynchronous Self-stabilizing Spanning Tree
• Self-stabilizing Space Optimal Synchronization Algorithms on Trees
• Acyclic strategy for silent self-stabilization in spanning forests
• A self-stabilizing distributed algorithm to construct an arbitrary spanning tree of a connected graph

Cites work

• scientific article; zbMATH DE number 732976 (Why is no real title available?)
• scientific article; zbMATH DE number 2036567 (Why is no real title available?)
• scientific article; zbMATH DE number 2061549 (Why is no real title available?)
• A New Self-stabilizing Minimum Spanning Tree Construction with Loop-Free Property
• A Snap-Stabilizing DFS with a Lower Space Requirement
• A new polynomial silent stabilizing spanning-tree construction algorithm
• A self-stabilizing algorithm for constructing breadth-first trees
• An O(n)-time self-stabilizing leader election algorithm
• Competitive self-stabilizing \(k\)-clustering
• Distributed network protocols
• Introduction to Distributed Self-Stabilizing Algorithms
• Memory requirements for silent stabilization
• Parallel Processing and Applied Mathematics
• Proof labeling schemes
• Self-stabilization
• Self-stabilization with \(r\)-operators
• Self-stabilization with r-Operators Revisited
• Self-stabilizing depth-first search
• Self-stabilizing disconnected components detection and rooted shortest-path tree maintenance in polynomial steps
• Self-stabilizing extensions for message-passing systems
• Self-stabilizing leader election in optimal space under an arbitrary scheduler
• Self-stabilizing leader election in polynomial steps
• Self-stabilizing systems in spite of distributed control
• Snap-stabilizing tasks in anonymous networks
• The Conic toolkit for building distributed systems
• The expressive power of snap-stabilization
• The first fully polynomial stabilizing algorithm for BFS tree construction
• Universal dynamic synchronous self-stabilization

Cited in

(4)

• Self-stabilizing Space Optimal Synchronization Algorithms on Trees
• Acyclic strategy for silent self-stabilization in spanning forests
• Self-stabilizing disconnected components detection and rooted shortest-path tree maintenance in polynomial steps
• Analysis of a memory-efficient self-stabilizing BFS spanning tree construction

This page was built for publication: Optimized silent self-stabilizing scheme for tree-based constructions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2072099)