AF: Small: Distributed Optimization Beyond Worst Case Topologies

AF：小型：超越最坏情况拓扑的分布式优化

基本信息

批准号：
1910588
负责人：
Bernhard Haeupler
金额：
$ 40万
依托单位：
Carnegie-Mellon University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2019
资助国家：
美国
起止时间：
2019-07-15 至 2022-06-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1910588&HistoricalAwards=false
关键词：
AF Small Distributed Optimization Beyond

项目摘要

The modern computation and information processing systems shaping our world are ever increasing in scale and have become massively distributed. A fundamental understanding of distributed algorithms and optimization problems has in the past and inevitably will in the future lead to more efficient, more scalable, and overall vastly more powerful systems and applications with broad impacts on society. With this goal in mind, this project is developing an algorithmic toolbox for designing distributed optimization algorithms which drastically outperform state-of-the-art algorithms on non-worst-case topologies, common in practice. The project will also contribute greatly to the education and professional training of students in this critical field. The project plans to integrate research and education through curriculum development activities spanning graduate and undergraduate courses and provides initiatives and concrete steps taken by the project team to attract, excite, mentor, and support students from underrepresented groups.The shift towards massively distributed systems in practice has led to an increased interest and fast acceleration in our theoretical understanding of distributed optimization problems. However much of this work focuses on the algorithmic performance in worst-case topologies. Real world networks, however, do not always exhibit worst-case behavior and most networks of interest do not share the limiting bottleneck characteristics which dominate the current analyses of worst-case algorithms and their provable performance guarantees. In particular, there is no known barrier for ultra-fast polylogarithmic round distributed algorithms on any network of interest, while most current algorithms require Theta(sqrt(n)) rounds on any (such) topology, mostly because such a running time can be shown to be necessary on some practically irrelevant pathologically bad topologies. This almost exponential gap between worst-case-optimal Theta(sqrt(n)) algorithms and the ultra-fast performance which is likely possible in many, if not all, real-world settings motivates this project. This project provides a detailed program for designing instance-optimal distributed algorithms. Instance-optimal algorithms are competitive with the best algorithm on any given topology and thereby constitute the strongest possible form of algorithmically adjusting to non-worst-case topologies.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

塑造我们世界的现代计算和信息处理系统的规模不断扩大，并且变得大规模分布。对分布式算法和优化问题的基本理解在过去和将来都将不可避免地带来更高效、更可扩展、总体上更强大的系统和应用程序，对社会产生广泛影响。考虑到这一目标，该项目正在开发一个算法工具箱，用于设计分布式优化算法，该算法在实践中常见的非最坏情况拓扑上远远优于最先进的算法。该项目还将极大地促进这一关键领域学生的教育和专业培训。该项目计划通过涵盖研究生和本科生课程的课程开发活动将研究和教育结合起来，并提供项目团队为吸引、激励、指导和支持代表性不足群体的学生而采取的举措和具体步骤。实践中向大规模分布式系统的转变引起了我们对分布式优化问题的理论理解的兴趣增加和快速加速。然而，这项工作的大部分重点是最坏情况拓扑中的算法性能。然而，现实世界的网络并不总是表现出最坏情况的行为，并且大多数感兴趣的网络并不具有限制瓶颈特征，这些特征主导了当前对最坏情况算法及其可证明性能保证的分析。特别是，在任何感兴趣的网络上超快速多对数轮分布式算法都不存在已知的障碍，而大多数当前算法需要在任何（此类）拓扑上进行 Theta(sqrt(n)) 轮，主要是因为这样的运行时间可以是事实证明，这对于一些实际上不相关的病态不良拓扑是必要的。最坏情况下的最优 Theta(sqrt(n)) 算法与超快性能之间几乎呈指数级的差距，这在许多（如果不是全部）现实世界设置中可能是可能的，这激励了这个项目。该项目提供了用于设计实例最优分布式算法的详细程序。实例最优算法可与任何给定拓扑上的最佳算法相媲美，从而构成针对非最坏情况拓扑进行算法调整的最强可能形式。该奖项反映了 NSF 的法定使命，并通过使用基金会的评估进行评估，被认为值得支持。智力价值和更广泛的影响审查标准。

项目成果

期刊论文数量（29）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Synchronization Strings and Codes for Insertions and Deletions – a Survey

用于插入和删除的同步字符串和代码 — 调查

DOI：
10.1109/tit.2021.3056317
发表时间：
2021-01
期刊：
IEEE Transactions on Information Theory
影响因子：
2.5
作者：
Haeupler, Bernhard;Shahrasbi, Amirbehshad
通讯作者：
Shahrasbi, Amirbehshad

Universally-Optimal Distributed Shortest Paths and Transshipment via Graph-Based L1-Oblivious Routing

通过基于图的 L1 不经意路由实现通用最优分布式最短路径和转运

DOI：
发表时间：
2022-01
期刊：
Proceedings of the ACM-SIAM Symposium on Discrete Algorithms
影响因子：
0
作者：
Zuzic, Goran;Goranci, Gramoz;Ye, Mingquan;Haeupler, Bernhard;Sun, Xiaorui
通讯作者：
Sun, Xiaorui

Maximum Length-Constrained Flows and Disjoint Paths: Distributed, Deterministic and Fast

最大长度约束流和不相交路径：分布式、确定性和快速

DOI：
发表时间：
2023-01
期刊：
ACM Symposium on Theory of Computing
影响因子：
0
作者：
Haeupler, Bernhard;Hershkowitz, D Ellis;Saranurak, Thatchaphol
通讯作者：
Saranurak, Thatchaphol

Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization

通过去随机化改进分布式网络分解、命中集和扳手

DOI：
发表时间：
2023-01
期刊：
ACM-SIAM Symposium on Discrete Algorithms (SODA
影响因子：
0
作者：
Ghaffari, Mohsen;Grunau, Christoph;Haeupler, Bernhard;Ilchi, Saeed;Rozhoň, Václav
通讯作者：
Rozhoň, Václav

Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances

并行广度优先搜索和精确最短路径以及更强的近似距离概念

DOI：
发表时间：
2023-01
期刊：
ACM Symposium on Theory of Computing
影响因子：
0
作者：
Rozhoň, Václav;Haeupler, Bernhard;Martinsson, Anders;Grunau, Christoph;Zuzic, Goran
通讯作者：
Zuzic, Goran