2026-08-08T04:31:25Z https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:14803 2024-03-06T10:54:53Z ddc:004 open_access
The Quest for Universally-Optimal Distributed Algorithms (Invited Talk) Haeupler, Bernhard Distributed algorithms Many distributed optimization algorithms achieve an existentially-optimal round complexity (of (OΜƒ(√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: - What network topology parameters determine the complexity of distributed optimization? - Are there universally-optimal algorithms that are as fast as possible on every single topology? This talk provides an overview over the freshly-completed 6-year program that resolves these 25-year-old open problems for a wide class of global network optimization problems including MST, (1+Ξ΅)-min cut, various approximate shortest path problems, sub-graph connectivity, etc. We provide several equivalent graph parameters that are tight universal lower bounds for the above problems, fully characterizing their inherent complexity. We also give the first universally-optimal algorithms approximately achieving this complexity on every topology. The quest for universally-optimal distributed algorithms required novel techniques that also answer fundamental (open) questions in seemingly unrelated fields, such as, network information theory, approximation algorithms, (oblivious) packet routing, (algorithmic & topological) graph theory, and metric embeddings. Generally, the problems addressed in these fields explicitly or implicitly ask to jointly optimize 𝓁_∞ & 𝓁₁ parameters such as congestion & dilation, communication rate & delay, capacities & diameters of subnetworks, or the makespan of packet routings. In particular, results obtained on the way include the following firsts: (Congestion+Dilation)-Competitive Oblivious Routing, Network Coding Gaps for Completion-Times, Hop-Constrained Expanders & Expander Decompositions, Bi-Criteria (Online / Demand-Robust) 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 M. Ghaffari, G. Zuzic, D.E. Hershkowitz, D. Wajc, J. Li, H. Raecke, T. Izumi) Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik Bernhard Haeupler 2021 Is Part Of LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2021.1 urn:nbn:de:0030-drops-148030 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.1 eng https://creativecommons.org/licenses/by/4.0/legalcode