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

现代计算系统正变得越来越大，并且越来越分散。由于缺乏集中控制，系统组件之间的通信成为必要，以便同步计算和协调动作。在整个网络中传播信息也需要通信。在几乎所有分布式环境中，通信既是效率的瓶颈，同时也是错误和不可靠性的最大来源。该项目旨在研究通过编码减少通信量的可能性，同时仍然提供强大的可靠性保证。虽然将通信的可靠性和效率作为中心主题，但该项目对交互式和以网络为中心的分布式设置的关注使其与典型的信息和编码理论设置不同，后者通常是（i）静态的，（ii）有两个或少量恒定数量的参与方和（iii）假设信息是单向的，即，从一方发送到另一方。该项目的总体目标是为未来分布式系统中快速可靠的通信和计算奠定基础，并因此影响未来的技术和整个社会。该项目是NSF-BSF合作奋进的一部分。这两个相对初级的PI在设计和调整分布式设置的编码程序方面有着强大而广泛的记录，无论是单独还是合作。他们在编码和分布式计算方面的优势相互补充，这些协同作用已经导致了几个联合出版物和关于该项目主题的进一步初步成果。该项目的一个主要目标是扩大和加强美国与以色列的合作，并为研究生加入这项研究提供资金。该项目包括将研究与教育相结合的详细计划，例如，在研究生课程、本科生课程和研讨会的课程发展活动中纳入研究方向、课题和成果。该项目还提出了吸引、激发、招募和指导来自代表性不足群体的学生以及本科生的倡议和具体步骤，并将他们融入概述的研究中。无线电网络和网络编码：无线电网络是网络编码技术应用和发展的绝佳环境。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.