AF: Small: Distributed Optimization Beyond Worst Case Topologies
AF:小型:超越最坏情况拓扑的分布式优化
基本信息
- 批准号:1910588
- 负责人:
- 金额:$ 40万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:2019
- 资助国家:美国
- 起止时间:2019-07-15 至 2022-06-30
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
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的法定任务,并通过使用该基金会的知识优点和广泛的interia来评估来评估NSF的法定任务。
项目成果
期刊论文数量(29)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Rate-Distance Trade-offs for List-Decodable Insertion-Deletion Codes
- DOI:10.1109/itw54588.2022.9965935
- 发表时间:2020-09
- 期刊:
- 影响因子:0
- 作者:Bernhard Haeupler;Amirbehshad Shahrasbi
- 通讯作者:Bernhard Haeupler;Amirbehshad Shahrasbi
Hop-constrained oblivious routing
跳数约束的不经意路由
- DOI:10.1145/3406325.3451098
- 发表时间:2021
- 期刊:
- 影响因子:0
- 作者:Ghaffari, Mohsen;Haeupler, Bernhard;Zuzic, Goran
- 通讯作者:Zuzic, Goran
A Time-Optimal Randomized Parallel Algorithm for MIS
- DOI:10.1137/1.9781611976465.172
- 发表时间:2021-01
- 期刊:
- 影响因子:0
- 作者:M. Ghaffari;Bernhard Haeupler
- 通讯作者:M. Ghaffari;Bernhard Haeupler
Tree embeddings for hop-constrained network design
用于跳数受限网络设计的树嵌入
- DOI:10.1145/3406325.3451053
- 发表时间:2021
- 期刊:
- 影响因子:0
- 作者:Haeupler, Bernhard;Hershkowitz, D. Ellis;Zuzic, Goran
- 通讯作者:Zuzic, Goran
Low-Congestion shortcuts without embedding
无需嵌入的低拥塞快捷方式
- DOI:10.1007/s00446-020-00383-2
- 发表时间:2021
- 期刊:
- 影响因子:1.3
- 作者:Haeupler, Bernhard;Izumi, Taisuke;Zuzic, Goran
- 通讯作者:Zuzic, Goran
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Bernhard Haeupler其他文献
A Cut-Matching Game for Constant-Hop Expanders
恒定跳扩展器的剪切匹配游戏
- DOI:
- 发表时间:
2022 - 期刊:
- 影响因子:0
- 作者:
Bernhard Haeupler;Jonas Hübotter;M. Ghaffari - 通讯作者:
M. Ghaffari
Bounded-Contention Coding for the additive network model
加性网络模型的有界竞争编码
- DOI:
- 发表时间:
2015 - 期刊:
- 影响因子:1.3
- 作者:
K. Censor;Bernhard Haeupler;N. Lynch;M. Médard - 通讯作者:
M. Médard
Improved bounds and parallel algorithms for the Lovasz Local Lemma
改进 Lovasz 局部引理的边界和并行算法
- DOI:
- 发表时间:
2015 - 期刊:
- 影响因子:0
- 作者:
Bernhard Haeupler;David G. Harris - 通讯作者:
David G. Harris
Global computation in a poorly connected world: fast rumor spreading with no dependence on conductance
连接不良的世界中的全局计算:谣言快速传播,不依赖于电导
- DOI:
10.1145/2213977.2214064 - 发表时间:
2011 - 期刊:
- 影响因子:3.3
- 作者:
K. Censor;Bernhard Haeupler;Jonathan A. Kelner;P. Maymounkov - 通讯作者:
P. Maymounkov
Analyzing Network Coding (Gossip) Made Easy
- DOI:
10.1145/1993636.1993676 - 发表时间:
2011-06 - 期刊:
- 影响因子:0
- 作者:
Bernhard Haeupler - 通讯作者:
Bernhard Haeupler
Bernhard Haeupler的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Bernhard Haeupler', 18)}}的其他基金
CAREER: A Theory of Error Correction for Interactive Communication
职业:交互式通信的纠错理论
- 批准号:
1750808 - 财政年份:2018
- 资助金额:
$ 40万 - 项目类别:
Continuing Grant
CCF-BSF: AF: Small: Coding for Distributed Computing
CCF-BSF:AF:小型:分布式计算编码
- 批准号:
1618280 - 财政年份:2016
- 资助金额:
$ 40万 - 项目类别:
Standard Grant
AF: Small: Distributed Algorithms for Near-Planar Networks
AF:小型:近平面网络的分布式算法
- 批准号:
1527110 - 财政年份:2015
- 资助金额:
$ 40万 - 项目类别:
Standard Grant
相似国自然基金
面向海量小容量分布式资源节点的虚拟电厂调控优化研究
- 批准号:
- 批准年份:2021
- 资助金额:30 万元
- 项目类别:青年科学基金项目
面向海量小容量分布式资源节点的虚拟电厂调控优化研究
- 批准号:62103325
- 批准年份:2021
- 资助金额:24.00 万元
- 项目类别:青年科学基金项目
面向异构信息传输的分布式低轨小卫星星群对地协同传输机制研究
- 批准号:61801295
- 批准年份:2018
- 资助金额:26.0 万元
- 项目类别:青年科学基金项目
基于小电容的动态无功补偿及其对分布式发电接入配电网的电压稳定控制研究
- 批准号:51777063
- 批准年份:2017
- 资助金额:61.0 万元
- 项目类别:面上项目
面向小语种的高性能文本情感分析关键技术研究
- 批准号:61762091
- 批准年份:2017
- 资助金额:43.0 万元
- 项目类别:地区科学基金项目
相似海外基金
AF:Small: Distributed Protocols for Information Dissemination in Ad-Hoc Radio Networks
AF:Small:Ad-Hoc 无线电网络中信息传播的分布式协议
- 批准号:
2153723 - 财政年份:2022
- 资助金额:
$ 40万 - 项目类别:
Standard Grant
AF: Small: Distributed Algorithms for Dynamic, Noisy Platforms: Wireless Networks, Robot Swarms, and Insect Colonies
AF:小型:适用于动态、嘈杂平台的分布式算法:无线网络、机器人群和昆虫群
- 批准号:
2003830 - 财政年份:2020
- 资助金额:
$ 40万 - 项目类别:
Standard Grant
AF: Small: Embedding Distributed Computations and Flows in Networks
AF:小型:在网络中嵌入分布式计算和流程
- 批准号:
1909363 - 财政年份:2019
- 资助金额:
$ 40万 - 项目类别:
Standard Grant
AF: Small: Locality and Energy in Distributed Computing
AF:小:分布式计算中的局部性和能量
- 批准号:
1815316 - 财政年份:2018
- 资助金额:
$ 40万 - 项目类别:
Standard Grant
CCF-BSF: AF: Small: Convex and Non-Convex Distributed Learning
CCF-BSF:AF:小:凸和非凸分布式学习
- 批准号:
1718970 - 财政年份:2018
- 资助金额:
$ 40万 - 项目类别:
Standard Grant