License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2018.31
URN: urn:nbn:de:0030-drops-98207
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9820/
Ghaffari, Mohsen ;
Li, Jason
New Distributed Algorithms in Almost Mixing Time via Transformations from Parallel Algorithms
Abstract
We show that many classical optimization problems - such as (1 +/- epsilon)-approximate maximum flow, shortest path, and transshipment - can be computed in tau_{mix}(G)* n^o(1) rounds of distributed message passing, where tau_{mix}(G) is the mixing time of the network graph G. This extends the result of Ghaffari et al. [PODC'17], whose main result is a distributed MST algorithm in tau_{mix}(G)* 2^O(sqrt{log n log log n}) rounds in the CONGEST model, to a much wider class of optimization problems. For many practical networks of interest, e.g., peer-to-peer or overlay network structures, the mixing time tau_{mix}(G) is small, e.g., polylogarithmic. On these networks, our algorithms bypass the Omega(sqrt n+D) lower bound of Das Sarma et al. [STOC'11], which applies for worst-case graphs and applies to all of the above optimization problems. For all of the problems except MST, this is the first distributed algorithm which takes o(sqrt n) rounds on a (nontrivial) restricted class of network graphs.
Towards deriving these improved distributed algorithms, our main contribution is a general transformation that simulates any work-efficient PRAM algorithm running in T parallel rounds via a distributed algorithm running in T * tau_{mix}(G)* 2^O(sqrt{log n}) rounds. Work- and time-efficient parallel algorithms for all of the aforementioned problems follow by combining the work of Sherman [FOCS'13, SODA'17] and Peng and Spielman [STOC'14]. Thus, simulating these parallel algorithms using our transformation framework produces the desired distributed algorithms.
The core technical component of our transformation is the algorithmic problem of solving multi-commodity routing - that is, roughly, routing n packets each from a given source to a given destination - in random graphs. For this problem, we obtain a new algorithm running in 2^O(sqrt{log n}) rounds, improving on the 2^O(sqrt{log n log log n}) round algorithm of Ghaffari, Kuhn, and Su [PODC'17]. As a consequence, for the MST problem in particular, we obtain an improved distributed algorithm running in tau_{mix}(G)* 2^O(sqrt{log n}) rounds.
BibTeX - Entry
@InProceedings{ghaffari_et_al:LIPIcs:2018:9820,
author = {Mohsen Ghaffari and Jason Li},
title = {{New Distributed Algorithms in Almost Mixing Time via Transformations from Parallel Algorithms}},
booktitle = {32nd International Symposium on Distributed Computing (DISC 2018)},
pages = {31:1--31:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-092-7},
ISSN = {1868-8969},
year = {2018},
volume = {121},
editor = {Ulrich Schmid and Josef Widder},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9820},
URN = {urn:nbn:de:0030-drops-98207},
doi = {10.4230/LIPIcs.DISC.2018.31},
annote = {Keywords: Distributed Graph Algorithms, Mixing Time, Random Graphs, Multi-Commodity Routing}
}
|
Keywords: |
|
Distributed Graph Algorithms, Mixing Time, Random Graphs, Multi-Commodity Routing |
|
Collection: |
|
32nd International Symposium on Distributed Computing (DISC 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
04.10.2018 |
