caa a22 4500 555285499 20190715031130.0 cr unu---uuuuu 190206s2018 xx s 100 0 eng 10.3929/ethz-b-000315336 doi 10.4230/LIPIcs.DISC.2018.31 doi (ETHRESEARCH)oai:www.research-collection.ethz.ch:20.500.11850/315336 Ghaffari Mohsen New distributed algorithms in almost mixing time via transformations from parallel algorithms [Elektronische Daten] [Mohsen Ghaffari, Jason Li, Ulrich Schmid (Editor), Josef Widder (Editor)] Leibniz int. proc. inform. Dagstuhl Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2018 Open access ethresearch 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. 32nd International Symposium on Distributed Computing (DISC 2018) in New Orleans, LA, USA (October 15-19, 2018) Creative Commons Attribution 3.0 Unported http://creativecommons.org/licenses/by/3.0 ethresearch Distributed Graph Algorithms ethresearch Mixing Time ethresearch Random Graphs ethresearch Multi-Commodity Routing ethresearch Li Jason joint author Schmid Ulrich Editor edt Widder Josef Editor edt 32nd International Symposium on Distributed Computing (DISC 2018) Dagstuhl : Schloss Dagstuhl - Leibniz-Zentrum für Informatik pp. 31:1-31:16 978-3-95977-092-7 http://hdl.handle.net/20.500.11850/315336 text/html WWW-Backlink auf das Repository (Open access) 1 Conference Paper ethresearch ETHRESEARCH 856 40 http://hdl.handle.net/20.500.11850/315336 text/html WWW-Backlink auf das Repository (Open access) ETHRESEARCH 100 1- Ghaffari Mohsen ETHRESEARCH 700 1- Li Jason joint author ETHRESEARCH 700 1- Schmid Ulrich Editor edt ETHRESEARCH 700 1- Widder Josef Editor edt ETHRESEARCH 773 0- 32nd International Symposium on Distributed Computing (DISC 2018) Dagstuhl : Schloss Dagstuhl - Leibniz-Zentrum für Informatik pp. 31:1-31:16 978-3-95977-092-7 BK010053 XK010053 XK010000 ETHRESEARCH ETHRESEARCH ETHRESEARCH Conference Paper Open access