We show that many classical optimization problems --- such as $(1\pm\epsilon)$-approximate maximum flow, shortest path, and transshipment --- can be computed in $\newcommand{\tmix}{{\tau_{\text{mix}}}}\tmix(G)\cdot n^{o(1)}$ rounds of distributed message passing, where $\tmix(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 $\tmix(G)\cdot 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 $\tmix(G)$ is small, e.g., polylogarithmic. On these networks, our algorithms bypass the $\tilde\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\cdot \tmix(G)\cdot 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 \emph{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...

Thanks. We have received your report. If we find this content to be in
violation of our guidelines,
we will remove it.

Ok