CIF: Small: Information Recovery Under Connectivity and Communication Constraints

现代大规模分布式存储系统将数据存储在数以千计的存储节点上，单个节点发生故障是系统运行的日常现实。维护存储系统的公司会为节点故障做好准备，依靠擦除码来确保数据完整性。虽然近年来开发的专门编码方法涉及对于这种系统可能的最少量的节点间通信，但大多数当前的解决方案依赖于节点之间的通用连接的共同假设。同时，在许多从物联网开始的应用中，节点之间的连接是基于影响节点彼此通信或与数据收集器通信的能力的物理接近或类似特征而建立的。考虑到这一点，本项目研究了在具有有限连通性的系统中的数据恢复方法，其中数据修复的成本由节点之间的路径长度控制，因此取决于网络的拓扑。本项目旨在建立数据恢复的通信复杂性的基本极限，该极限考虑了底层网络的连通性属性，并构建了确保数据完整性的编码方法，以防止节点故障、错误信息或接近最小可能通信量的界限的敌对行动。作为网络性能的一个指标，本项目的研究目的是调查随机网络中数据恢复的限度，并量化随机网络中高概率恢复和不可能恢复之间的阈值。这个项目还研究了在通信约束下纠正错误的代码的代数构造，包括代数曲线上的代码，以及合作修复模型的最佳修复代码。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Modern-day large-scale distributed storage systems store data on thousands of storage nodes, and failure of individual nodes is everyday reality of the system operation. Companies maintaining storage systems make provisions for node failures, relying on erasure codes to ensure data integrity. While specialized encoding methods developed in recent years involve minimum amount of inter-nodal communication possible for such systems, most current solutions rely on the common assumption of universal connectivity between the nodes. At the same time, in many applications starting with Internet-of Things, connections between the nodes are established based on physical proximity or similar features that affect the ability of the nodes to communicate with each other or with the data collector. With this in mind, this project investigates methods of data recovery in systems with limited connectivity whereby the cost of data repair is governed by the length of the path between the nodes, and therefore depends on the topology of the network.This project intends to establish fundamental limits of communication complexity of data recovery that account for connectivity properties of the underlying network as well as to construct coding methods that ensure data integrity against node failures, incorrect information, or adversarial action that approach the bounds on the minimum possible amount of communication. As an indicator of the network properties, the research conducted in this project aims to investigate limits of data recovery in random networks and to quantify thresholds between high-probability recovery and the impossibility of recovery in random networks. This project also examines algebraic constructions of codes that correct errors under communication constraints including codes on algebraic curves, and optimal-repair codes for the cooperative repair model.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.