CCF-BSF: AF: Small: Coding for Distributed Computing

CCF-BSF：AF：小型：分布式计算编码

基本信息

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

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1618280&HistoricalAwards=false
关键词：
CCF BSF AF Small Coding

项目摘要

Modern computing systems are getting drastically larger and increasingly distributed. The lack of centralized control necessitates communication between the system components in order to synchronize computations and coordinate actions. Communication is also needed to disseminate information throughout the network. In almost all distributed settings communication is both a bottleneck for efficiency and simultaneously the largest source of errors and unreliability. This project aims to study the possibilities of reducing the amount of communication through coding while still providing strong reliability guarantees. While having reliability and efficiency of communication as a central theme the focus of this project on interactive and network-centric distributed settings sets it apart from classical information and coding theory settings which are typically (i) static, (ii) have two or a small constant number of parties and (iii) assume that information is one-directional, i.e., sent from one party to another. The overall goal of this project is to contribute to the foundation for fast and reliable communication and computation in the distributed systems of tomorrow and as such influence tomorrow's technologies and society at large. This project is part of an NSF-BSF collaborative endeavor. The two relatively junior PIs have a strong and extensive track-record in designing and adapting coding procedures for distributed settings, both individually and collaboratively. Their strengths in coding and distributed computing complement each other well and these synergies have already lead to several joint publications and further preliminary results on the topics of this project. A major goal of this project is to extend and strengthen this US-Israeli collaboration and provide funding for graduate students to join this research. The project includes detailed plans for integrating research and education, e.g., by including research directions, topics and results in curriculum development activities spanning graduate courses, undergraduate courses and seminars. The project also puts forward initiatives and concrete steps to attract, excite, recruit, and mentor students from underrepresented groups as well as undergraduate students and integrate them in the outlined research.The project focuses on two distributed settings in which the development and application of novel coding techniques has a potentially large impact:? Radio Networks and Network Coding: Radio networks are an excellent setting for the application and development of network coding techniques. The PIs will pursue several ideas which allow to exploit the additivity of the wireless medium, which usually considered harmful due to causing collisions, by employing coding. They will also consider extensions to the classical radio network models which more faithfully reflect characteristics of real radio networks, in particular the uncertainty of message delivery and explore ways to alleviate those effects with coding approaches.? Error Correction for Interactive Communication in Distributed Networks: The PIs will attack several questions and approaches to develop coding techniques that allow any distributed computation to become robust against corruptions in their communications, a question that has not been explored sufficiently so far. This builds on recent advanced in coding schemes for interactive two-party and multi-party protocols.

现代计算系统越来越大，并且越来越分布。缺乏集中控制需要系统组件之间的通信，以便同步计算和协调操作。还需要进行沟通以在整个网络中传播信息。在几乎所有分布式设置中，通信既是效率的瓶颈，又是最大的错误和不可靠的来源。该项目旨在研究通过编码减少通信量的可能性，同时仍提供强大的可靠性保证。尽管具有可靠性和沟通作为中心主题，但该项目的重点还是以交互式和网络为中心的分布式设置将其与经典信息和编码理论设置区分开来，这些设置通常是（i）静态的，（ii）具有两个或少数恒定的派对，并且（iii）假定信息是一个方向，即从一个方向发送到另一个聚会。该项目的总体目标是为明天的分布式系统中的快速和可靠的沟通和计算做出贡献，并因此影响了明天的技术和整个社会。该项目是NSF-BSF协作努力的一部分。这两个相对少年的PI在设计和调整分布式设置的编码程序方面具有强大而广泛的轨道记录，无论是单独还是协作的。它们在编码和分发计算方面的优势相互补充，这些协同作用已经导致了几个联合出版物，并进一步就该项目的主题进行了初步结果。该项目的一个主要目标是扩展和加强这项美国 - 以色列的合作，并为研究生加入这项研究提供资金。该项目包括整合研究和教育的详细计划，例如，包括研究方向，主题和结果，包括研究生课程，本科课程和研讨会的课程发展活动。该项目还提出了倡议和具体步骤，以吸引，兴奋，招募和指导来自代表性不足的小组以及本科生的学生，并将其整合到概述的研究中。该项目着重于两个分布式设置，在这些设置中，新颖的编码技术的开发和应用具有潜在的大影响力影响：无线电网络和网络编码：无线电网络是网络编码技术应用和开发的绝佳设置。 PI将追求几个想法，这些想法允许利用无线介质的添加性，这些介质通常因使用编码而被认为是由于造成碰撞而有害的。他们还将考虑对经典无线网络模型的扩展，该模型更忠实地反映了真实无线电网络的特征，特别是消息传递的不确定性并探索如何通过编码方法来减轻这些影响的方法。分布式网络中交互式通信的错误纠正：PIS将攻击几个问题和方法，以开发编码技术，这些技术使任何分布式计算都可以抵抗其通信中的损坏，这一问题迄今尚未得到充分探讨。这是基于互动式两方和多方协议的最新高级编码方案的基础。

项目成果

期刊论文数量（38）

专著数量（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