NSF-BSF: CIF: Small: From storage codes to recoverable systems

现代数据中心以分布式形式存储大量信息，将相同数据文件的部分放在系统中的不同服务器上，其中服务器经常发生故障。由于暂时或永久故障而无法访问的服务器上的数据的恢复关键取决于数据编码的方法，而开发这种方法是大型存储系统设计的主要方向。该项目旨在根据服务器之间的连接性质（如空间接近性或通信链路的可用性）构建数据编码方法，以考虑低成本的数据恢复。这代表了广泛研究的数据重建问题的转变，该问题低估了基于系统拓扑在服务器之间移动数据的不同成本，并为设计有效的数据编码和重建方法提供了新的数学方法的可能性。在第一部分中，该项目基于最近发现的计算机科学和应用数学工具在代码设计中的应用来推进高密度存储系统。在第二部分中，该项目涉及大型存储系统，旨在建立数据编码方法的新统计属性，以及在保持恢复功能的同时可以存储在系统中的数据量的限制。本项目旨在开发解决大规模分布式存储数据编码问题的新方法。由于包含数据块的码字的不同部分存储在不同的服务器上，因此有效的恢复取决于从故障存储节点附近的服务器重构不可用数据的能力。用技术术语来说，系统由一个图来描述，其中码字的坐标存储在不同的顶点上，每个顶点的值是图中相邻顶点值的函数。在第一部分中，本项目旨在基于最近建立的存储码、索引码和低密度量子码之间的联系构建高效的编码方法。主要目标是构建尽可能高速率的代码，以及开发迭代程序，以恢复各种类型图的多个节点，这些图依赖于它们的代数性质和有限图的渗透理论方法。该项目的第二部分涉及支持无限图（如整数图，二维整数晶格等）上的数据恢复的编码系统，使用约束系统，符号动力学和熵理论的方法，以建立存储在大型系统中的最大可能的数据密度。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Modern-day data centers store large volumes of information in distributed form, placing parts of the same data file on different servers in the system wherein server failures occur on a regular basis. Recovery of data located on servers that become unavailable because of transient or permanent failures critically depends on the methods of data encoding, and developing such methods is the main directions in the design of large-scale storage systems. This project aims at constructing methods of data encoding that account for low-cost data recovery based on the nature of connections between the servers such as spatial proximity or the availability of communication links. This represents a shift from the broadly studied problems of data reconstruction that discount the varying cost of moving data between the servers based on the topology of the system, and opens a possibility of engaging new mathematical methods for the design of efficient methods of data encoding and reconstruction. In the first part, this project advances high-density storage systems based on recently discovered applications of tools from computer science and applied mathematics to the code design. In the second part, the project addresses large-size storage systems, aiming to establish new statistical properties of methods of data encoding as well as the limits on the volume of data that can be stored in the system while maintaining the recovery functionality.This project aims at developing new methods in the problems of data coding for large-scale distributed storage. Since different parts of the codeword comprising a chunk of data are stored on different servers, efficient recovery hinges on the ability to reconstruct unavailable data from the servers that are in close proximity of the failed storage node. In technical terms, the system is described by a graph where coordinates of the codeword are stored on different vertices, and the value of each vertex is a function of the values of its neighbors in the graph. In the first part, this project aims at constructing efficient encoding methods based on recently established connections between codes for storage, index codes, and low-density quantum codes. The main goals are constructing codes of the highest possible rate as well as developing iterative procedures for the recovery of multiple nodes for various classes of graphs relying on their algebraic properties and on methods from percolation theory on finite graphs. The second part of the project is concerned with coding systems that support data recovery on infinite graphs such as the graph of integers, the two-dimensional integer lattice and the like, using methods from constrained systems, symbolic dynamics, and entropy theory for the purpose of establishing the maximum possible density of data stored in large-scale systems.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.