Fault-Tolerant Labeling and Compact Routing Schemes

DOI10.1145/3465084.3467929MaRDI QIDQ6201973zbMATH OpenOpenAlexFDO

Authors Michal Dory, M. Parter

Publication date 26 March 2024

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

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

zbMATH Keywords

fault-tolerant labeling schemesfault-tolerant routing schemes

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

Abstract: The paper presents fault-tolerant (FT) labeling schemes for general graphs, as well as, improved FT routing schemes. For a given $n$-vertex graph $G$ and a bound $f$ on the number of faults, an $f$-FT connectivity labeling scheme is a distributed data structure that assigns each of the graph edges and vertices a short label, such that given the labels of the vertices $s$ and $t$, and at most $f$ failing edges $F$, one can determine if $s$ and $t$ are connected in $GsetminusF$. The primary complexity measure is the length of the individual labels. Since their introduction by [Courcelle, Twigg, STACS '07], compact FT labeling schemes have been devised only for a limited collection of graph families. In this work, we fill in this gap by proposing two (independent) FT connectivity labeling schemes for general graphs, with a nearly optimal label length. This serves the basis for providing also FT approximate distance labeling schemes, and ultimately also routing schemes. Our main results for an $n$-vertex graph and a fault bound $f$ are: -- There is a randomized FT connectivity labeling scheme with a label length of $O(f+logn)$ bits, hence optimal for $f=O(logn)$. This scheme is based on the notion of cycle space sampling [Pritchard, Thurimella, TALG '11]. -- There is a randomized FT connectivity labeling scheme with a label length of $O(lo{g}^{3}n)$ bits (independent of the number of faults $f$). This scheme is based on the notion of linear sketches of [Ahn et al., SODA '12]. -- For $kgeq1$, there is a randomized routing scheme that routes a message from $s$ to $t$ in the presence of a set $F$ of faulty edges, with stretch $O(|F{|}^{2}k)$ and routing tables of size $ildeO(f^3{n}^{1/k})$. This significantly improves over the state-of-the-art bounds by [Chechik, ICALP '11], providing the first scheme with sub-linear FT labeling and routing schemes for general graphs.

Cited in

(5)

• Near-optimal distributed computation of small vertex cuts
• Deterministic fault-tolerant connectivity labeling scheme
• Connectivity oracles for predictable vertex failures
• Connectivity labeling in faulty colored graphs
• Near-optimal vertex fault-tolerant labels for Steiner connectivity

This page was built for publication: Fault-Tolerant Labeling and Compact Routing Schemes

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