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的法定使命,并通过使用基金会的知识价值和更广泛的影响审查标准进行评估,被认为值得支持。

项目成果

期刊论文数量(29)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
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
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
Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances
并行广度优先搜索和精确最短路径以及更强的近似距离概念
  • DOI:
  • 发表时间:
    2023
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Rozhoň, Václav;Haeupler, Bernhard;Martinsson, Anders;Grunau, Christoph;Zuzic, Goran
  • 通讯作者:
    Zuzic, Goran
Tree embeddings for hop-constrained network design
用于跳数受限网络设计的树嵌入
  • DOI:
    10.1145/3406325.3451053
  • 发表时间:
    2021
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Haeupler, Bernhard;Hershkowitz, D. Ellis;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其他文献

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
A Cut-Matching Game for Constant-Hop Expanders
恒定跳扩展器的剪切匹配游戏
  • DOI:
  • 发表时间:
    2022
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Bernhard Haeupler;Jonas Hübotter;M. Ghaffari
  • 通讯作者:
    M. Ghaffari
Explicit Capacity Approaching Coding for Interactive Communication
显式能力接近交互式通信编码
Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity Certificates
确定性分布式稀疏和超稀疏 Spanner 和连接证书

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

相似国自然基金

昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
  • 批准号:
  • 批准年份:
    2024
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
  • 批准号:
    n/a
  • 批准年份:
    2022
  • 资助金额:
    10.0 万元
  • 项目类别:
    省市级项目
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
  • 批准号:
    32000033
  • 批准年份:
    2020
  • 资助金额:
    24.0 万元
  • 项目类别:
    青年科学基金项目
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
  • 批准号:
    31972324
  • 批准年份:
    2019
  • 资助金额:
    58.0 万元
  • 项目类别:
    面上项目
变异链球菌small RNAs连接LuxS密度感应与生物膜形成的机制研究
  • 批准号:
    81900988
  • 批准年份:
    2019
  • 资助金额:
    21.0 万元
  • 项目类别:
    青年科学基金项目
基于small RNA 测序技术解析鸽分泌鸽乳的分子机制
  • 批准号:
    31802058
  • 批准年份:
    2018
  • 资助金额:
    26.0 万元
  • 项目类别:
    青年科学基金项目
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
  • 批准号:
    31870821
  • 批准年份:
    2018
  • 资助金额:
    56.0 万元
  • 项目类别:
    面上项目
Small RNA介导的DNA甲基化调控的水稻草矮病毒致病机制
  • 批准号:
    31772128
  • 批准年份:
    2017
  • 资助金额:
    60.0 万元
  • 项目类别:
    面上项目
基于small RNA-seq的针灸治疗桥本甲状腺炎的免疫调控机制研究
  • 批准号:
    81704176
  • 批准年份:
    2017
  • 资助金额:
    20.0 万元
  • 项目类别:
    青年科学基金项目
水稻OsSGS3与OsHEN1调控small RNAs合成及其对抗病性的调节
  • 批准号:
    91640114
  • 批准年份:
    2016
  • 资助金额:
    85.0 万元
  • 项目类别:
    重大研究计划

相似海外基金

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
AF: Small: Relaxed Distributed Data Structures: Implementations and Applications
AF:小:宽松的分布式数据结构:实现和应用
  • 批准号:
    1816922
  • 财政年份:
    2018
  • 资助金额:
    $ 40万
  • 项目类别:
    Standard Grant
AF: Small: Collaborative Research: Distributed Quasi-Newton Methods for Nonsmooth Optimization
AF:小:协作研究:非光滑优化的分布式拟牛顿方法
  • 批准号:
    1717391
  • 财政年份:
    2017
  • 资助金额:
    $ 40万
  • 项目类别:
    Standard Grant
AF: Small: Collaborative Research: Distributed Quasi-Newton Methods for Nonsmooth Optimization
AF:小:协作研究:非光滑优化的分布式拟牛顿方法
  • 批准号:
    1717154
  • 财政年份:
    2017
  • 资助金额:
    $ 40万
  • 项目类别:
    Standard Grant
AF: Small: Collaborative Research: Distributed Quasi-Newton Methods for Nonsmooth Optimization
AF:小:协作研究:非光滑优化的分布式拟牛顿方法
  • 批准号:
    1717207
  • 财政年份:
    2017
  • 资助金额:
    $ 40万
  • 项目类别:
    Standard Grant
CCF-BSF: AF: Small: Coding for Distributed Computing
CCF-BSF:AF:小型:分布式计算编码
  • 批准号:
    1618280
  • 财政年份:
    2016
  • 资助金额:
    $ 40万
  • 项目类别:
    Standard Grant
AF: Small: Complexity of Distributed Storage
AF:小:分布式存储的复杂性
  • 批准号:
    1526725
  • 财政年份:
    2015
  • 资助金额:
    $ 40万
  • 项目类别:
    Standard Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了