Fast routing table construction using small messages: extended abstract
Fast routing table construction using small messages: extended abstract
复制标题
DOI：
10.1145/2488608.2488656
复制
发表时间：
2012-10
期刊：
影响因子：
--
通讯作者：
C. Lenzen;B. Patt-Shamir
中科院分区：
文献类型：
--
作者：
C. Lenzen;B. Patt-Shamir
我们描述了一种分布式随机算法来构造路由表。当给定0< ε <= 1/2时，算法运行时间为~O(n1/2+ε + HD)，其中n为节点数，HD为网络的跳数（即假设网络没有加权）。生成的路径加权长度最多等于最优加权长度的O（ε-1log ε-1）倍。这是第一个打破计算单个源加权最短路径的复杂度障碍的算法。此外，对于路由表和近似距离的分布式计算，该算法几乎满足~Omega（n1/2 + HD）下界（对于ε=1/log n，其最优性可达多对数因子）。所提出的方法有许多应用，包括改进的广义斯坦纳森林分布近似算法、全对距离估计和加权直径估计。
We describe a distributed randomized algorithm to construct routing tables. Given 0< ε <= 1/2, the algorithm runs in time ~O(n1/2+ε + HD), where n is the number of nodes and HD denotes the diameter of the network in hops (i.e., as if the network is unweighted). The weighted length of the produced routes is at most O(ε-1log ε-1) times the optimal weighted length. This is the first algorithm to break the Omega(n) complexity barrier for computing weighted shortest paths even for a single source. Moreover, the algorithm nearly meets the ~Omega(n1/2 + HD) lower bound for distributed computation of routing tables and approximate distances (with optimality, up to polylog factors, for ε=1/log n). The presented techniques have many applications, including improved distributed approximation algorithms for Generalized Steiner Forest, all-pairs distance estimation, and estimation of the weighted diameter.