Dual failure resilient BFS structure

DOI10.1145/2767386.2767408MaRDI QIDQ2796286zbMATH OpenOpenAlexFDO

Authors M. Parter

Publication date 23 March 2016

Published in Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

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

zbMATH Keywords

fault-tolerancelower boundsreplacement-paths

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Reliability, testing and fault tolerance of networks and computer systems (68M15) Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Abstract: We study {em breadth-first search (BFS)} spanning trees, and address the problem of designing a sparse {em fault-tolerant} BFS structure, or {em FT-BFS } for short, resilient to the failure of up to two edges in the given undirected unweighted graph $G$, i.e., a sparse subgraph $H$ of $G$ such that subsequent to the failure of up to two edges, the surviving part $H^{\prime }$ of $H$ still contains a BFS spanning tree for (the surviving part of) $G$. FT-BFS structures, as well as the related notion of replacement paths, have been studied so far for the restricted case of a single failure. It has been noted widely that when concerning shortest-paths in a variety of contexts, there is a sharp qualitative difference between a single failure and two or more failures. Our main results are as follows. We present an algorithm that for every $n$-vertex unweighted undirected graph $G$ and source node $s$ constructs a (two edge failure) FT-BFS structure rooted at $s$ with $O(n^{5/3})$ edges. To provide a useful theory of shortest paths avoiding 2 edges failures, we take a principled approach to classifying the arrangement these paths. We believe that the structural analysis provided in this paper may decrease the barrier for understanding the general case of $fgeq2$ faults and pave the way to the future design of $f$-fault resilient structures for $fgeq2$. We also provide a matching lower bound, which in fact holds for the general case of $fgeq1$ and multiple sources $SsubseteqV$. It shows that for every $fgeq1$, and integer $1leqsigmaleqn$, there exist $n$-vertex graphs with a source set $SsubseteqV$ of cardinality $sigma$ for which any FT-BFS structure rooted at each $sinS$, resilient to up to $f$-edge faults has $Omega(sigm{a}^{1/(f+1)}cdot{n}^{2-1/(f+1)})$ edges.

Recommendations

• Multiple source dual fault tolerant BFS trees
• Fault Tolerant Approximate BFS Structures
• Sparse Fault-Tolerant BFS Structures
• Fault-tolerant approximate BFS structures
• Sparse fault-tolerant BFS trees
• Fault tolerant approximate BFS structures with additive stretch
• Computational and Information Science
• Fault-tolerant broadcast graphs

Cites work

• scientific article; zbMATH DE number 826255 (Why is no real title available?)
• Memorization and Association on a Realistic Neural Model

Cited in

(29)

• Fault-tolerant approximate shortest-path trees
• Graph spanners: a tutorial review
• Multiple-edge-fault-tolerant approximate shortest-path trees
• Output sensitive fault tolerant maximum matching
• \textit{Renaissance}: a self-stabilizing distributed SDN control plane using in-band communications
• Fault tolerant approximate BFS structures with additive stretch
• Sparse fault-tolerant BFS trees
• Fault-tolerant approximate BFS structures
• Fault-tolerant subgraph for single-source reachability: general and optimal
• Conditional hardness for sensitivity problems
• Sparse Fault-Tolerant BFS Structures
• Generic single edge fault tolerant exact distance oracle
• Multiple source dual fault tolerant BFS trees
• Sparse weight tolerant subgraph for single source shortest path
• New results on linear size distance preservers
• Reachability Preservers: New Extremal Bounds and Approximation Algorithms
• Distributed constructions of dual-failure fault-tolerant distance preservers
• Near-optimal distributed computation of small vertex cuts
• An efficient strongly connected components algorithm in the fault tolerant model
• New extremal bounds for reachability and strong-connectivity preservers under failures
• New fault tolerant subset preservers
• New extremal bounds for reachability and strong-connectivity preservers under failures
• Near optimal algorithm for fault tolerant distance oracle and single source replacement path problem
• Deterministic replacement path covering
• Restorable shortest path tiebreaking for edge-faulty graphs
• Fault tolerant max-cut
• Connectivity labeling in faulty colored graphs
• Fault-tolerant bounded flow preservers
• Optimal sensitivity oracle for Steiner mincut

This page was built for publication: Dual failure resilient BFS structure

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