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和标准带宽限制的网络（交通拥堵模型），该项目旨在获得在O（d）同步回合中运行的有效分布式算法，以解决重要的标准优化问题，例如最大流量，最小跨度树和各种最短路径问题。这种方法非常及时地连接到最近的，深远的，分布式的下限，这些下限表明（稀疏）绘制了许多优化问题，无法计算或什至在小于欧米茄（SQRT（n））的圆圈中近似。 PI认为，该提案为分布式网络优化算法的理论提供了一个令人兴奋的新方向，并就平面和近平面图的算法研究提供了新的观点。期望这个更广泛的研究方向和该项目的具体初步结果将引起社区的兴趣，并作为进行更大，更广泛调查的基础。

项目成果

期刊论文数量（32）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Making Asynchronous Distributed Computations Robust to Noise

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

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

Explicit Binary Tree Codes with Polylogarithmic Size Alphabet

DOI：
10.1145/3188745.3188928
发表时间：
2018-01-01
期刊：
STOC'18: PROCEEDINGS OF THE 50TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING
影响因子：
0
作者：
Cohen, Gil;Haeupler, Bernhard;Schulman, Leonard J.
通讯作者：
Schulman, Leonard J.

Network Coding Gaps for Completion Times of Multiple Unicasts