Universally-optimal distributed algorithms for known topologies
Universally-optimal distributed algorithms for known topologies
复制标题
DOI：
10.1145/3406325.3451081
复制
发表时间：
2021-04
期刊：
影响因子：
--
通讯作者：
Bernhard Haeupler;David Wajc;Goran Zuzic
中科院分区：
文献类型：
--
作者：
Bernhard Haeupler;David Wajc;Goran Zuzic
许多分布式优化算法实现了现有的运行时间，这意味着存在一些病理最差的拓扑结构，没有算法可以做得更好，大多数感兴趣的网络都可以呈指数级的算法。网络拓扑参数确定分布式优化的复杂性吗？我们解决了已知的25岁的开放问题（即支持的拥塞），以解决一系列全球网络优化问题，包括MST，（1+є） - 切割，各种近似最短的路径问题，Sub Sub - 图形连接等。特别是，我们提供了几个（等效的）图参数，并向它们展示上述问题的紧密通用下限，完全表征了他们的继承复杂性还意味着基于低结构快捷框架的算法与上述下限相匹配，如果快捷方式有效地近似，它们通常是最佳的。
Many distributed optimization algorithms achieve existentially-optimal running times, meaning that there exists some pathological worst-case topology on which no algorithm can do better. Still, most networks of interest allow for exponentially faster algorithms. This motivates two questions: (i) What network topology parameters determine the complexity of distributed optimization? (ii) Are there universally-optimal algorithms that are as fast as possible on every topology? We resolve these 25-year-old open problems in the known-topology setting (i.e., supported CONGEST) for a wide class of global network optimization problems including MST, (1+є)-min cut, various approximate shortest paths problems, sub-graph connectivity, etc. In particular, we provide several (equivalent) graph parameters and show they are tight universal lower bounds for the above problems, fully characterizing their inherent complexity. Our results also imply that algorithms based on the low-congestion shortcut framework match the above lower bound, making them universally optimal if shortcuts are efficiently approximable.