Please use this identifier to cite or link to this item:
Title: Efficient distributed approximation algorithms via probabilistic tree embeddings
Authors: Khan, Maleq.
Kuhn, Fabian.
Malkhi, Dahlia.
Pandurangan, Gopal.
Talwar, Kunal.
Issue Date: 2012
Source: Khan, M., Kuhn, F., Malkhi, D., Pandurangan, G., & Talwar, K. (2012). Efficient distributed approximation algorithms via probabilistic tree embeddings. Distributed Computing, 25(3), 189-205.
Series/Report no.: Distributed computing
Abstract: 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.
DOI: 10.1007/s00446-012-0157-9
Fulltext Permission: none
Fulltext Availability: No Fulltext
Appears in Collections:SPMS Journal Articles

Citations 10

Updated on Jan 23, 2023

Web of ScienceTM
Citations 10

Updated on Feb 6, 2023

Page view(s) 50

Updated on Feb 6, 2023

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.