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., peertopeer 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 worstcase 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 workefficient 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 timeefficient 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 multicommodity 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:131:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770927},
ISSN = {18688969},
year = {2018},
volume = {121},
editor = {Ulrich Schmid and Josef Widder},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9820},
URN = {urn:nbn:de:0030drops98207},
doi = {10.4230/LIPIcs.DISC.2018.31},
annote = {Keywords: Distributed Graph Algorithms, Mixing Time, Random Graphs, MultiCommodity Routing}
}
04.10.2018
Keywords: 

Distributed Graph Algorithms, Mixing Time, Random Graphs, MultiCommodity Routing 
Seminar: 

32nd International Symposium on Distributed Computing (DISC 2018)

Issue date: 

2018 
Date of publication: 

04.10.2018 