Abstract: Many distributed optimization algorithms achieve an existentially-optimal round complexity (of ($\tilde{O}(\sqrt{n} + D)$), i.e., there exists some pathological worst-case topology on which no algorithm can be faster. However, most networks of interest allow for exponentially faster algorithms. This motivates two questions:
(1) What network topology parameters determine the complexity of distributed optimization?
(2) Are there universally-optimal algorithms that are as fast as possible on every single topology?
This talk summarizes the results of a freshly-completed 7-year program that affirmatively resolves these 25-year-old open problems for a wide class of global network optimization problems including MST, $(1+\epsilon)$-min cut, various approximate shortest path problems, solving Laplacian systems, sub-graph connectivity, etc.. In particular, we provide several equivalent graph parameters that are tight universal lower bounds for all problems above, fully characterizing their inherent complexity. We also give universally-optimal algorithms approximately achieving this complexity on every topology.
The quest for universally-optimal distributed algorithms required novel techniques that also answer fundamental questions in seemingly unrelated fields, such as, network information theory, (oblivious) packet routing, approximation algorithms, (algorithmic & topological) graph theory, and metric embeddings. Generally, the problems addressed in these fields explicitly or implicitly ask to jointly optimize $\ell_\infty$ & $\ell_1$ parameters such as congestion & length, communication rate & delay, connectivity & diameters of subnetworks, or makespan. In particular, results obtained on the way include: Hop Constrained Expanders & Expander Decompositions, (Congestion+Dilation)-Competitive Oblivious Routing, Network Coding Gaps for Completion-Times, (Online) Approximation Algorithms for many Diameter-Constrained Network Design Problems (e.g., (Group) Steiner Tree/Forest), Makespan-Competitive (Compact and Distributed) Routing Tables, and (Probabilistic) Tree Embeddings for Hop-Constrained Distances.
(joint work with Mohsen Ghaffari; my awesome CMU students Goran Zuzic, Ellis D. Hershkowitz, David Wajc & Jason Li; Harald Raecke; Taisuke Izumi)