AF: Small: Distributed Algorithms for Near-Planar Networks

AF：小型：近平面网络的分布式算法

• 批准号: 1527110
• 负责人: Bernhard Haeupler
• 金额: $ 45万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-06-15 至 2018-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1527110&HistoricalAwards=false
• 关键词: AF; Small; Distributed; Algorithms; Near

The goal of this project is the development of an algorithmic toolbox to design efficient distributed algorithms for planar and near-planar networks. (Informally, a planar network is one that can be drawn on a two-dimensional surface without any lines crossing.) Many real-world networks and optimization problem instances have a near-planar structure that allows for simpler, more efficient, and often more practical algorithms. The study of such network structures and their algorithmic implications has been a very successful endeavor with a rich theory, many versatile tools, significant algorithmic advances, and drastic performance improvements on problem instances of interest. While modern systems become increasingly larger and more distributed, little is known about how distributed algorithms can be improved on near-planar instances. This project aims to change this and to bring similar improvements to the distributed setting. While its scope is primarily theoretical, the algorithms and general principles to be developed have the potential of laying the groundwork for practical algorithms with real-world impacts. The project will also have a broad educational impact. Much of the research will be done by or in collaboration with graduate students. Furthermore, the proposed research direction features many theoretical questions suitable for undergraduate students without extensive background knowledge and also provides opportunities for experiments and implementation projects. Lastly, the interdisciplinary nature of the problem will likely foster many collaborations between the PI and other researchers in different fields. Any tools and algorithms developed will be shared publicly.This project will initiate the principled study of distributed algorithms for planar and near-planar networks. In particular, for networks with diameter D and standard bandwidth-limitations (CONGEST model), the project aims at obtaining efficient distributed algorithms running in O(D) synchronous rounds for important standard optimization problems like maximum flow, minimum spanning tree, and various shortest path problems. This approach very timely connects to recent, far-reaching, distributed lower bounds which show that in general (sparse) graphs many optimization problems cannot be computed or even crudely approximated in less than Omega(sqrt(n))-rounds. The PI believes that this proposal provides an exciting new direction for the theory of distributed network optimization algorithms and gives a new perspective on the algorithmic study of planar and near-planar graphs. The expectation is that this broader research direction and the concrete initial results coming out of this project will spark the interest of the community and serve as a basis for a larger and more extensive investigation.

这个项目的目标是开发一个算法工具箱，为平面和近平面网络设计高效的分布式算法。（非正式地，平面网络是可以在二维表面上绘制而没有任何线交叉的网络。许多现实世界的网络和优化问题实例都具有近平面结构，可以实现更简单、更高效、更实用的算法。这种网络结构及其算法的影响的研究一直是一个非常成功的奋进与丰富的理论，许多通用的工具，显着的算法进步，并大幅提高性能的问题感兴趣的实例。虽然现代系统变得越来越大，越来越分布式，很少有人知道如何分布式算法可以改善近平面的实例。这个项目旨在改变这一点，并为分布式设置带来类似的改进。虽然其范围主要是理论性的，但要开发的算法和一般原则有可能为具有现实影响的实用算法奠定基础。该项目还将产生广泛的教育影响。大部分研究将由研究生完成或与研究生合作完成。此外，拟议的研究方向具有许多理论问题，适合本科生没有广泛的背景知识，也提供了实验和实施项目的机会。最后，这个问题的跨学科性质可能会促进PI和不同领域的其他研究人员之间的许多合作。任何开发的工具和算法都将公开共享。本项目将启动平面和近平面网络分布式算法的原理性研究。特别是，对于直径为D和标准带宽限制（CONGEST模型）的网络，该项目旨在获得O（D）同步轮中运行的高效分布式算法，以解决重要的标准优化问题，如最大流，最小生成树和各种最短路径问题。这种方法非常及时地连接到最近的，影响深远的，分布式的下界，这表明在一般（稀疏）图中，许多优化问题不能计算，甚至粗略地近似于小于Omega（sqrt（n））轮。PI认为，这一建议为分布式网络优化算法理论提供了一个令人兴奋的新方向，并为平面和近平面图的算法研究提供了一个新的视角。我们期望，这个更广泛的研究方向和具体的初步结果出来，这个项目将引发社会的兴趣，并作为一个更大和更广泛的调查的基础。

项目成果

Network Coding Gaps for Completion Times of Multiple Unicasts

• DOI: 10.1109/focs46700.2020.00053
• 发表时间: 2019-05
• 期刊: 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)
• 作者: Bernhard Haeupler;David Wajc;Goran Zuzic

Making Asynchronous Distributed Computations Robust to Noise

使异步分布式计算对噪声具有鲁棒性

• DOI: 10.4230/lipics.itcs.2018.50
• 发表时间: 2018
• 期刊: ACM-SIGACT Innovations in Theoretical Computer Science Conference
• 作者: Censor-Hillel, Keren;Gelles, Ran;Haeupler, Bernhard
• 通讯作者: Haeupler, Bernhard

Minor Excluded Network Families Admit Fast Distributed Algorithms

少数被排除在外的网络家族承认快速分布式算法

• DOI: 10.1145/3212734.3212776
• 发表时间: 2018
• 期刊: ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing
• 作者: Haeupler, Bernhard;Li, Jason;Zuzic, Goran
• 通讯作者: Zuzic, Goran

Efficient Linear and Affine Codes for Correcting Insertions/Deletions

• DOI: 10.1137/1.9781611976465.1
• 发表时间: 2020-07
• 作者: Kuan Cheng;V. Guruswami;Bernhard Haeupler;Xin Li

Synchronization Strings: List Decoding for Insertions and Deletions

• DOI: 10.4230/lipics.icalp.2018.76
• 发表时间: 2018-02
• 期刊: ArXiv
• 作者: Bernhard Haeupler;Amirbehshad Shahrasbi;M. Sudan