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

NSF-BSF：CIF：小型：从存储代码到可恢复系统

• 批准号: 2110113
• 负责人: Alexander Barg
• 金额: $ 50万
• 依托单位: University of Maryland, College Park
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-07-01 至 2024-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2110113&HistoricalAwards=false
• 关键词: NSF; BSF; CIF; Small; storage

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.

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

项目成果

High-Rate Storage Codes on Triangle-Free Graphs

无三角形图上的高速存储代码

• DOI: 10.1109/tit.2022.3191309
• 发表时间: 2022
• 期刊: IEEE Transactions on Information Theory
• 影响因子: 2.5
• 作者: Barg, Alexander;Zemor, Gilles
• 通讯作者: Zemor, Gilles

Interior-point regenerating codes on graphs

图上的内点重新生成代码

• 发表时间: 2022
• 期刊: IEEE International Symposium on Information Theory
• 作者: Patra, A.;Barg, A.
• 通讯作者: Barg, A.

Node Repair on Connected Graphs

• DOI: 10.1109/tit.2022.3145824
• 发表时间: 2021-08
• 期刊: IEEE Transactions on Information Theory
• 影响因子: 2.5
• 作者: Adway Patra;A. Barg

Recoverable Systems on Lines and Grids

线路和电网上的可恢复系统

• 发表时间: 2022
• 期刊: IEEE International Symposium on Information Theory
• 作者: Barg, A.;Elishco, O.;Gabrys, R.;Yaakobi, E.
• 通讯作者: Yaakobi, E.

A construction of maximally recoverable codes

• DOI: 10.1007/s10623-022-01020-8
• 发表时间: 2021-08
• 期刊: Designs, Codes and Cryptography
• 作者: A. Barg;Zitan Chen;Itzhak Tamo