Efficient Distributed Approximation Algorithms via Probabilistic Tree Embeddings

We present a uniform approach to design efficient distributed approximation algorithms for various network optimization problems. Our approach is randomized and based on a probabilistic tree embedding due to Fakcharoenphol, Rao, and Talwar [12] (FRT embedding). We show how to efficiently compute an (implicit) FRT embedding in a decentralized manner and how to use the embedding to obtain expected O(logn)-approximate distributed algorithms for the generalized Steiner forest problem, the minimum routing cost spanning tree problem, and the k-source shortest paths problem in arbitrary networks. The time complexities of our algorithms are within a polylogarithmic factor of the optimum. The distributed construction of the FRT embedding is based on the computation of least elements (LE) lists, a distributed data structure that can be of independent interest. Assuming a global order on the nodes of a network, the LE list of a node stores the smallest node (with respect to the given order) within every distance d (cf. Cohen [6], Cohen and Kaplan [7]). For weighted graphs, we give an almost-optimal distributed algorithm for computing LE lists, assuming a random order on the nodes. For unweighted graphs, our LE lists computation has asymptotically optimal time complexity O(D), where D is the diameter of the network. As a byproduct, we get an improved leader election algorithm in general networks that is both time-optimal and almost message-optimal with high probability.