2026-07-23T22:07:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9820 2024-03-06T10:45:00Z ddc:004 open_access

New Distributed Algorithms in Almost Mixing Time via Transformations from Parallel Algorithms Ghaffari, Mohsen Li, Jason Distributed Graph Algorithms Mixing Time Random Graphs Multi-Commodity Routing 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mohsen Ghaffari and Jason Li 2018 Is Part Of LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2018.31 urn:nbn:de:0030-drops-98207 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.31 eng https://creativecommons.org/licenses/by/3.0/legalcode