Efficient distributed approximation algorithms via probabilistic tree embeddings
Efficient distributed approximation algorithms via probabilistic tree embeddings
复制标题
通过概率树嵌入的高效分布式逼近算法
DOI：
--
复制
发表时间：
2008
影响因子：
1.3
通讯作者：
Kunal Talwar
中科院分区：
文献类型：
--
作者：
Maleq Khan;F. Kuhn;D. Malkhi;Gopal Pandurangan;Kunal Talwar
我们提出了一种统一的方法来为各种基本网络优化问题设计有效的分布式近似算法。我们的方法是随机的，并且基于 Fakcharoenphol 等人提出的概率树嵌入。 （J Comput Syst Sci 69(3):485–497, 2004）（FRT 嵌入）。我们展示了如何以分散的方式有效计算（隐式）FRT 嵌入，以及如何使用嵌入获得针对各种问题的高效预期 O(log n) 近似分布式算法，特别是广义 Steiner 森林问题（包括最小 Steiner 树问题）、最小路由成本生成树问题和 k 源最短路径问题。 FRT 嵌入的分布式构造基于最小元素 (LE) 列表的计算，这是一种独立的分布式数据结构。假设网络节点上存在全局顺序，节点的 LE 列表存储每个距离 d 内的最小节点（相对于给定顺序）（参见 Cohen in J Comput Syst Sci 55(3):441–453, 1997，Cohen and Kaplan in J Comput Syst Sci 73(3):265–288, 2007）。假设节点上的顺序是随机的，我们给出了一种在时间复杂度为 O(S log n) 的加权图上计算 LE 列表的分布式算法，其中 S 是称为最短路径直径的图参数，可以将其视为图的直径 D 的加权对应项。对于未加权图，我们的 LE 列表计算具有 O(D) 的渐近最优时间复杂度。作为副产品，我们得到了一种改进的通用网络同步领导者选举算法，该算法既是时间最优的，又是高概率的几乎消息最优的。
We present a uniform approach to design efficient distributed approximation algorithms for various fundamental network optimization problems. Our approach is randomized and based on a probabilistic tree embedding due to Fakcharoenphol et al. (J Comput Syst Sci 69(3):485–497, 2004) (FRT embedding). We show how to efficiently compute an (implicit) FRT embedding in a decentralized manner and how to use the embedding to obtain efficient expected O(log n)-approximate distributed algorithms for various problems, in particular the generalized Steiner forest problem (including the minimum Steiner tree problem), the minimum routing cost spanning tree problem, and the k-source shortest paths problem. The distributed construction of the FRT embedding is based on the computation of least elements (LE) lists, a distributed data structure that is of independent interest. Assuming a global order on the nodes of a network, the LE-list of a node stores the smallest node (w.r.t. the given order) within every distance d (cf. Cohen in J Comput Syst Sci 55(3):441–453, 1997, Cohen and Kaplan in J Comput Syst Sci 73(3):265–288, 2007). Assuming a random order on the nodes, we give a distributed algorithm for computing LE-lists on a weighted graph with time complexity O(S log n), where S is a graph parameter called the shortest path diameter which can be considered the weighted counterpart of the diameter D of the graph. For unweighted graphs, our LE-lists computation has asymptotically optimal time complexity of O(D). As a byproduct, we get an improved synchronous leader election algorithm for general networks that is both time-optimal and almost message-optimal with high probability.