Distributed MST and Routing in Almost Mixing Time
Distributed MST and Routing in Almost Mixing Time
复制标题
DOI：
10.1145/3087801.3087827
复制
发表时间：
2017-07
期刊：
影响因子：
--
通讯作者：
M. Ghaffari;F. Kuhn;Hsin-Hao Su
中科院分区：
文献类型：
--
作者：
M. Ghaffari;F. Kuhn;Hsin-Hao Su
我们提出了一种随机分布式算法，该算法在τ（g）2o（√（log n log log n））中计算最小跨度树，在任何n节点Graph g中都具有混合时间τ（g）多种现实兴趣的次级复杂性，并且低于著名的ω（D+√n）Das Sarma等人的下限[stoc'11]在这个结果中的核心新颖性是在此问题中，分布式置换路由的方法，我们应在最短的时间内将一个数据包从每个源传递到其目的地我们在τ（g）2o（√（log n log n log n））弹中路由并传递所有这些数据包，假设每个节点V是最多DG（V）数据包的源或目的地。在此路线中结果是基本图上的良好膨胀随机图的一定层次嵌入，我们认为这很可能超出这项工作。
We present a randomized distributed algorithm that computes a minimum spanning tree in τ(G) · 2O(√(log n log log n))) rounds, in any n-node graph G with mixing time τ(G). This result provides a sub-polynomial complexity for a wide range of graphs of practical interest, and goes below the celebrated Ω(D+ √n) lower bound of Das Sarma et al. [STOC'11] which holds for some worst-case general graphs. The core novelty in this result is a distributed method for permutation routing. In this problem, one is given a number of source-destination pairs, and we should deliver one packet from each source to its destination, all in parallel, in the shortest span of time possible. Our algorithm allows us to route and deliver all these packets in τ(G) · 2O(√(log n log log n)) rounds, assuming that each node v is the source or destination for at most dG(v) packets. The main technical ingredient in this routing result is a certain hierarchical embedding of good-expansion random graphs on the base graph, which we believe can be of interest well beyond this work.