论文标题
更快的确定性所有对所有最短路径中的最短路径
Faster Deterministic All Pairs Shortest Paths in Congest Model
论文作者
论文摘要
我们提出了一种新的确定性算法，用于分布式加权的所有对最短路径（APSP）的分布式算法（APSP），均在无向图和有向图中。我们的算法以$ \ tilde {o}（n^{4/3}）$ rounds在具有任意边缘权重的图表上的圆形模型中运行，并且它在上一个$ \ tilde {o}（n^{3/2}）上有所改善。 [ARKP18]。我们的新算法的主要组件是一种用于确定性构建阻滞剂设置的新技术，并且是一种新的管道式方法，用于确定性地传播从源节点到网络中的阻止程序集节点的距离值。这两种技术都在其他分布式算法上具有潜在的应用。 我们用于计算阻滞剂集的新的确定性算法适应[BRS94]中的NC近似HyperGraph Set Cover算法，以适应阻滞剂集的分布式构造。它遵循首先设计仅使用成对独立性的随机算法的两步过程，然后使用线性大小的样品空间来降低该算法。该算法与我们的APSP算法中的第一步几乎相同，该算法在[ARKP18，AR19]中的确定性阻滞剂集合算法上的最短路径的最初步骤可显着改善，通过删除另外的$ n \ n \ cdot | $ q | $ q | $ q | $ q | $ q | $ ns Blocker ins q IS Q is the Blocker ins q is the Blocker。 我们的APSP算法中的另一个新组件是一种确定的管道方法，可以传播从源节点到阻滞剂节点的距离值。我们在此步骤中使用一种简单的天然圆形旋转方法，并使用合适的进度度量显示了它实现$ \ tilde {o}（n^{4/3}）$绑定在圆的数量上。看来，用于有效广播多个值的标准确定性方法，以及使用[HPDG+19，LSP19]中的路由时间表发送或接收消息的标准确定性方法，不适用于此设置。
We present a new deterministic algorithm for distributed weighted all pairs shortest paths (APSP) in both undirected and directed graphs. Our algorithm runs in $\tilde{O}(n^{4/3})$ rounds in the Congest models on graphs with arbitrary edge weights, and it improves on the previous $\tilde{O}(n^{3/2})$ bound of Agarwal et al. [ARKP18]. The main components of our new algorithm are a new faster technique for constructing blocker set deterministically and a new pipelined method for deterministically propagating distance values from source nodes to the blocker set nodes in the network. Both of these techniques have potential applications to other distributed algorithms. Our new deterministic algorithm for computing blocker set adapts the NC approximate hypergraph set cover algorithm in [BRS94] to the distributed construction of a blocker set. It follows the two-step process of first designing a randomized algorithm that uses only pairwise independence, and then derandomizes this algorithm using a sample space of linear size. This algorithm runs in almost the same number of rounds as the initial step in our APSP algorithm that computes $h$-hops shortest paths, and significantly improves on the deterministic blocker set algorithms in [ARKP18, AR19] by removing an additional $n\cdot |Q|$ term in the round bound, where Q is the blocker set. The other new component in our APSP algorithm is a deterministic pipelined approach to propagate distance values from source nodes to blocker nodes. We use a simple natural round-robin method for this step, and we show using a suitable progress measure that it achieve the $\tilde{O}(n^{4/3})$ bound on the number of rounds. It appears that the standard deterministic methods for efficiently broadcasting multiple values, and for sending or receiving messages using the routing schedule in [HPDG+19,LSP19] do not apply to this setting.
