Analysis of a memory-efficient self-stabilizing BFS spanning tree construction

DOI10.1016/J.TCS.2023.113804MaRDI QIDQ2697434zbMATH OpenOpenAlexFDO

Authors Ajoy K. Datta, Stéphane Devismes, Colette Johnen, Lawrence L. Larmore

Publication date 12 April 2023

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1907.07944

zbMATH Keywords

self-stabilizationround complexitystabilization timeBFS spanning treedistributed unfair daemon

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• The first fully polynomial stabilizing algorithm for BFS tree construction
• The first fully polynomial stabilizing algorithm for BFS tree construction
• Self-stabilizing depth-first search
• Optimized silent self-stabilizing scheme for tree-based constructions
• Time Optimal Asynchronous Self-stabilizing Spanning Tree

Cites work

• scientific article; zbMATH DE number 1332672 (Why is no real title available?)
• A self-stabilizing algorithm for constructing breadth-first trees
• A self-stabilizing algorithm for constructing spanning trees
• Compact deterministic self-stabilizing leader election on a ring: the exponential advantage of being talkative
• Introduction to Distributed Self-Stabilizing Algorithms
• Memory requirements for silent stabilization
• Self-stabilization of dynamic systems assuming only read/write atomicity
• Self-stabilizing depth-first search
• Self-stabilizing systems in spite of distributed control
• The Conic toolkit for building distributed systems
• The first fully polynomial stabilizing algorithm for BFS tree construction

Cited in

(1)

• A computational study of external-memory BFS algorithms

This page was built for publication: Analysis of a memory-efficient self-stabilizing BFS spanning tree construction

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