CIF: Small: Fundamental Tradeoffs Between Communication Load and Storage Resources in Distributed systems

未来的数据通信网络将必须支持遍布各地的大量设备，在飞行中收集，处理和传输数据。预计这样的网络将努力满足来自这样的数据通信需求的需求。同时，这些设备可以利用其廉价的分布式存储单元来降低交换信息的成本。一个关键的问题是，哪些数据应该放在存储器中，以便无论将来要求设备计算什么，满足这些请求的通信量都将尽可能小。系统可以用单次传输满足的设备越多，在减少传输次数方面的节省就越大。这些节省转化为降低的通信成本和在资源有限的设备上运行计算密集型和延迟关键型应用程序的能力。该项目旨在为未来的混合分层网络开发本地和有限存储资源的分布式计算的理论和算法基础，其中分布式设备协作解决大数据推理任务。尽管他们的基本性质，这项研究的结果是影响新兴的通信模式在工业中的设计。该项目还为学生开发了丰富的教育计划，他们将获得在竞争激烈，多样化和全球劳动力市场中取得成功的关键技能。本研究确定了与本地存储资源有限的分布式对等环境中的通信相关的关键问题。该项目的技术目标分为两个相关的推力：分布式缓存辅助的“雾无线接入网”架构和对等分布式数据洗牌。前一个问题模拟了为5G无线网络设想的混合网络架构，而后者在大数据和机器学习算法的分布式计算中找到了应用。两者共享缓存主题，即，利用本地存储来减少全局通信负载，但更重要的是，在交付或数据混洗阶段利用编码的分布式特性。伴随而来的技术问题在许多方面都是新颖的，并且跨越了信息论、编码理论和组合学。该研究包括创新的方法，以获得匡威和可实现的界限，可证明的性能保证。总体目标是为分布式计算开发一个基本框架，并对其他开放问题（如分布式索引编码和分布式干扰对齐）产生影响。该奖项反映了NSF的法定使命，并被认为值得通过使用基金会的知识价值和更广泛的影响审查标准进行评估来支持。

Future data communication networks will have to support multitude of devices abundantly spread all over, collecting, processing and transferring data on the fly. Such networks are expected to struggle to meet the demand from such data communication needs. At the same time, the devices can leverage their inexpensive and distributed memory units to reduce the cost of exchanging information. A key question is which data should be placed in the memories so that, irrespective of what the devices will be requested to compute in the future, the amount of communication to satisfy these requests will be the smallest possible. The more devices the system can satisfy with a single transmission, the larger the savings are in terms of reduction of the number of transmissions. These savings translate to reduced communication costs and an ability to run computation-intensive and latency-critical applications at resource-limited devices. This project aims to develop the theoretical and algorithmic foundation for distributed computation in presence of local and limited storage resources for future hybrid hierarchical networks, where distributed devices collaborate to solve big-data inference tasks. Despite their fundamental nature, the results of this research are impact the design of emerging communication models in industry. This project also develops a rich educational program for students, who will acquire critical skills to be successful in a competitive, diverse, and global workforce market.This research identifies critical questions related to communication in distributed peer-to-peer settings with local limited storage resources. The technical aims of the project are divided into two related thrusts: distributed cache-aided "Fog Radio Access Network" architectures and peer-to-peer distributed data shuffling. The former problem models the hybrid network architecture envisaged for 5G wireless networks, while the latter finds applications in distributed computation in big data and machine learning algorithms. Both share the caching theme, i.e., leverage local storage to reduce global communication load, but more importantly leverage the distributed nature of the encoding in either the delivery or data shuffling phase. The concomitant technical questions are novel in many aspects, and span information theory, coding theory, and combinatorics. The research includes innovative approaches to derive converse and achievable bounds, with provable performance guarantees. The overarching goal is to develop a fundamental framework for distributed computation, with implications to other open problems such as distributed index coding and distributed interference alignment.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.