Fault-tolerant spanners
From MaRDI portal
Publication:2943394
DOI10.1145/1993806.1993830zbMath1321.68103arXiv1101.5753OpenAlexW2146522997MaRDI QIDQ2943394
Robert Krauthgamer, Michael Dinitz
Publication date: 11 September 2015
Published in: Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1101.5753
Linear programming (90C05) Graph theory (including graph drawing) in computer science (68R10) Distributed systems (68M14) Approximation algorithms (68W25) Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed algorithms (68W15)
Related Items (20)
Invited talk: Resilient distributed algorithms ⋮ On resilient graph spanners ⋮ Improved Purely Additive Fault-Tolerant Spanners ⋮ Vertex fault tolerant additive spanners ⋮ Fault-Tolerant Subgraph for Single-Source Reachability: General and Optimal ⋮ Fault tolerant approximate BFS structures with additive stretch ⋮ An efficient strongly connected components algorithm in the fault tolerant model ⋮ Unnamed Item ⋮ Multipath Spanners via Fault-Tolerant Spanners ⋮ Sparse fault-tolerant spanners for doubling metrics with bounded hop-diameter or degree ⋮ Unnamed Item ⋮ Graph spanners: a tutorial review ⋮ Fault-tolerant approximate shortest-path trees ⋮ Connectivity Oracles for Graphs Subject to Vertex Failures ⋮ Distributed Spanner Approximation ⋮ Sparse Weight Tolerant Subgraph for Single Source Shortest Path ⋮ Output sensitive fault tolerant maximum matching ⋮ Fault tolerant additive and \((\mu, \alpha)\)-spanners ⋮ Distributed Distance-Bounded Network Design Through Distributed Convex Programming ⋮ Lasserre integrality gaps for graph spanners and related problems
Cites Work
- Unnamed Item
- Gradient clock synchronization in dynamic networks
- Consensus algorithms with one-bit messages
- Knowledge and common knowledge in a Byzantine environment: Crash failures
- Broadcasting in dynamic radio networks
- Programming simultaneous actions using common knowledge
- Continuous consensus via common knowledge
- Distributed computation in dynamic networks
- Flooding time in edge-Markovian dynamic graphs
- Knowledge and common knowledge in a distributed environment
- How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
- Opportunistic Information Dissemination in Mobile Ad-hoc Networks: The Profit of Global Synchrony
- Fault Tolerance in Networks of Bounded Degree
- Reaching Agreement in the Presence of Faults
- Perfectly secure message transmission
- Parsimonious flooding in dynamic graphs
- Optimal gradient clock synchronization in dynamic networks
- Almost-Everywhere Secure Computation
This page was built for publication: Fault-tolerant spanners
