The first fully polynomial stabilizing algorithm for BFS tree construction

DOI10.1016/J.IC.2019.01.005MaRDI QIDQ2272977zbMATH OpenOpenAlexWikidataFDO

Authors Alain Cournier, Vincent Villain, Stephane Rovedakis

Publication date 17 September 2019

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2019.01.005

zbMATH Keywords

distributed systemsfault tolerancespanning tree

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Review text

The paper introduces a new class of distributed algorithms for constructing a spanning tree and characterized by a round complexity polynomial on the network diameter and a step complexity polynomial on the network size, namely fully polynomial algorithms. Moreover, an example of such algorithm is provided for constructing a BFS tree under a distributed daemon; the BFS tree construction is based on a snap-stabilizing algorithm. The new class of distributed algorithms is particularly suitable in the context of large scale networks, while the algorithms allow to have an execution with a high degree of parallelism, while the communication complexity is bounded.

Recommendations

• The first fully polynomial stabilizing algorithm for BFS tree construction
• A new polynomial silent stabilizing spanning-tree construction algorithm
• Space efficient and time optimal distributed BFS tree construction
• A self-stabilizing distributed algorithm to construct an arbitrary spanning tree of a connected graph
• Time Optimal Asynchronous Self-stabilizing Spanning Tree

Cites work

• A new polynomial silent stabilizing spanning-tree construction algorithm
• A self-stabilizing algorithm for constructing breadth-first trees
• A self-stabilizing algorithm for constructing spanning trees
• A Snap-Stabilizing DFS with a Lower Space Requirement
• An O(n)-time self-stabilizing leader election algorithm
• Distributed network protocols
• scientific article; zbMATH DE number 4209563 (Why is no real title available?)
• Introduction to Distributed Algorithms
• Low communication self-stabilization through randomization
• Parallel Processing and Applied Mathematics
• Self-stabilization
• Self-stabilization with path algebra
• Self-stabilizing depth-first search
• 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
• The diameter of a scale-free random graph
• The first fully polynomial stabilizing algorithm for BFS tree construction
• Time Optimal Asynchronous Self-stabilizing Spanning Tree
• Time optimal self-stabilizing synchronization

Cited in

(7)

• Analysis of a memory-efficient self-stabilizing BFS spanning tree construction
• The first fully polynomial stabilizing algorithm for BFS tree construction
• A new polynomial silent stabilizing spanning-tree construction algorithm
• Communication efficient self-stabilizing leader election
• Asynchronous self-stabilization made fast, simple, and energy-efficient
• Being efficient in time, space, and workload: a self-stabilizing unison and its consequences
• Space efficient and time optimal distributed BFS tree construction

This page was built for publication: The first fully polynomial stabilizing algorithm for BFS tree construction

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