CIF: Small: Information Recovery Under Connectivity and Communication Constraints

CIF：小：连接和通信限制下的信息恢复

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

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.

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

项目成果

Cooperative Repair: Constructions of Optimal MDS Codes for All Admissible Parameters

• DOI: 10.1109/tit.2018.2856206
• 发表时间: 2018-01
• 期刊: IEEE Transactions on Information Theory
• 影响因子: 2.5
• 作者: Min Ye;A. Barg

Capacity of Dynamical Storage Systems

动态存储系统的容量

• DOI: 10.1109/tit.2020.3029427
• 发表时间: 2021
• 期刊: IEEE Transactions on Information Theory
• 影响因子: 2.5
• 作者: Elishco, Ohad;Barg, Alexander
• 通讯作者: Barg, Alexander

STOLARSKY'S INVARIANCE PRINCIPLE FOR FINITE METRIC SPACES

• DOI: 10.1112/mtk.12066
• 发表时间: 2021-01-01
• 期刊: MATHEMATIKA
• 影响因子: 0.8
• 作者: Barg, Alexander

Bounds for discrepancies in the Hamming space

汉明空间中差异的界限

• DOI: 10.1016/j.jco.2021.101552
• 发表时间: 2021
• 期刊: Journal of Complexity
• 影响因子: 1.7
• 作者: Barg, Alexander;Skriganov, Maxim
• 通讯作者: Skriganov, Maxim

Regenerating codes on graphs

在图表上重新生成代码

• DOI: 10.1109/isit45174.2021.9517983
• 发表时间: 2021
• 期刊: 2021 IEEE International Symposium on Information Theory
• 作者: Patra, Adway;Barg, Alexander
• 通讯作者: Barg, Alexander