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.
