论文标题
双重失效故障距离保存器的分布式结构
Distributed Constructions of Dual-Failure Fault-Tolerant Distance Preservers
论文作者
论文摘要
容错的距离保存器（跨度）是稀疏的子图，它们在边缘或顶点失败下给定的顶点对之间保持（近似）距离。这些结构是如此，主要是从集中观点研究的。尽管容错的保留剂的事实主要是由于分布式网络容易出错的性质而引起的，但在这些结构的分布式计算方面并不知道很多。 在本文中，我们介绍了用于构建容错距离保存器的分布式算法和$+2 $的添加跨度，这些算法最多可抵御\ emph {两个edge}故障。在我们工作之前，唯一已知的非平凡构造是\ emph {single}故障，\ emph {single source}设置了[ghaffari和parter spaa'16]。 我们的主要技术贡献是用于计算距离保存器W.R.T.的分布式算法。源顶点的子集$ s $，弹性到两个边缘故障。输出结构包含一个BFS $ bfs（s，g \ setMinus \ {e_1，e_2 \}）$ in s $中的每个$ s \ ins s $，每个$ e_1，e_1，e_2 \ in g $ in G $。该结构的分布式结构基于边缘充血（通过同时运行多个BFS树形成）与输出子图的稀疏性之间的微妙平衡。以前尚未知道构造这些结构的均匀旋转算法。
Fault tolerant distance preservers (spanners) are sparse subgraphs that preserve (approximate) distances between given pairs of vertices under edge or vertex failures. So-far, these structures have been studied mainly from a centralized viewpoint. Despite the fact fault tolerant preservers are mainly motivated by the error-prone nature of distributed networks, not much is known on the distributed computational aspects of these structures. In this paper, we present distributed algorithms for constructing fault tolerant distance preservers and $+2$ additive spanners that are resilient to at most \emph{two edge} faults. Prior to our work, the only non-trivial constructions known were for the \emph{single} fault and \emph{single source} setting by [Ghaffari and Parter SPAA'16]. Our key technical contribution is a distributed algorithm for computing distance preservers w.r.t. a subset $S$ of source vertices, resilient to two edge faults. The output structure contains a BFS tree $BFS(s,G \setminus \{e_1,e_2\})$ for every $s \in S$ and every $e_1,e_2 \in G$. The distributed construction of this structure is based on a delicate balance between the edge congestion (formed by running multiple BFS trees simultaneously) and the sparsity of the output subgraph. No sublinear-round algorithms for constructing these structures have been known before.
