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

现代计算系统正变得越来越大，越来越分散。由于缺乏集中控制，需要在系统组件之间进行通信，以便同步计算和协调行动。还需要通信来在整个网络中传播信息。在几乎所有的分布式环境中，通信既是效率的瓶颈，同时也是错误和不可靠的最大来源。该项目旨在研究通过编码减少通信量的可能性，同时仍然提供强大的可靠性保证。虽然通信的可靠性和效率是一个中心主题，但本项目对交互和以网络为中心的分布式环境的关注使其有别于典型的(I)静态的、(Ii)具有两个或少量恒定数量的各方以及(Iii)假设信息是单向的，即从一方发送到另一方的经典信息和编码理论设置。该项目的总体目标是为未来分布式系统中快速可靠的通信和计算奠定基础，并因此影响未来的技术和整个社会。该项目是NSF-BSF合作努力的一部分。这两个相对初级的私人投资主管在为分散的环境设计和调整编码程序方面有很强和广泛的记录，无论是单独还是合作。它们在编码和分布式计算方面的优势相辅相成，这些协同作用已经导致了关于该项目主题的几个联合出版物和进一步的初步结果。该项目的一个主要目标是扩大和加强美国和以色列的合作，并为研究生加入这项研究提供资金。该项目包括将研究与教育相结合的详细计划，例如，在研究生课程、本科课程和研讨会的课程开发活动中纳入研究方向、主题和结果。该项目还提出了计划和具体步骤，以吸引、激励、招募和指导来自代表性不足群体的学生以及本科生，并将他们整合到概述的研究中。该项目侧重于两个分布式环境，在这些环境中，新型编码技术的开发和应用具有潜在的巨大影响：？无线电网络和网络编码：无线电网络是网络编码技术应用和发展的极佳环境。PI将追求允许通过使用编码来利用无线介质的可加性的几个想法，无线介质的可加性通常被认为是由于引起冲突而有害的。他们还将考虑对经典无线电网络模型的扩展，以更真实地反映真实无线电网络的特征，特别是消息传递的不确定性，并探索通过编码方法来缓解这些影响的方法。分布式网络中交互通信的纠错：PI将攻击几个问题和方法，以开发编码技术，使任何分布式计算在其通信中变得健壮，这是一个到目前为止还没有充分探索的问题。这建立在交互式双方和多方协议的最新先进编码方案的基础上。

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.