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, Rao, and Talwar [16] (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 [8], Cohen and Kaplan [9]). 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.

In  Distributed Computing

Details