CIF: Small: Collaborative Research: Efficient Codes and their Performance Limits for Distributed Storage Systems

生成和收集的数据的爆炸式增长重新激起了人们对有效存储这些数据的兴趣。大型数据中心和分布式存储系统已经变得越来越普遍，在我们的日常计算任务中扮演着越来越重要的角色。虽然数据中心不应该丢失数据，但正如行业统计数据所证实的那样，磁盘故障每天都会发生。本项目开发的纠错码的方法和思想使系统能够更好地保证数据不丢失，并减少为了恢复由于磁盘故障而丢失的信息而需要移动的数据量。这个项目的另一个相关目标是减少支持恢复过程所需的存储开销。这些目标是通过依赖于构造数据编码过程的代数方法以及数据交换和恢复的新算法来实现的。总的来说，在这个项目中进行的研究有助于在大规模分布式存储系统中开发更有效的数据管理程序。基于局部恢复的概念，提出了一种新的数据编码和恢复的代数过程，使人们能够在开销和修复带宽之间实现折衷。该项目研究了从单个磁盘丢失中恢复的情况，这是系统中最常见的问题，以及从多个磁盘故障中恢复的情况，解决了数据编码中纠正一次擦除和多次擦除的问题。通过构造具有简单恢复步骤的最优局部可恢复码，得到了具有局部性要求的码距离的新界限。该项目还解决了从多个地点同时恢复数据的问题，增强了大规模分布式存储系统的数据可用性，这是21世纪经济的关键骨干组成部分。

The explosive growth of data being generated and collected has rekindled interest in efficient means of storing such data. Large data centers and distributed storage systems have become more widespread, playing an ever-increasing role in our everyday computational tasks. While a data center should never lose data, disk failures occur on a daily basis as confirmed by the industry statistics. Methods and ideas from error correcting codes developed in this project enable the system to provide better guarantees against data loss as well as to reduce the amount of data that needs to be moved in order to enable recovery of information lost due to disk failures. Another related goal of this project is the reduction of storage overhead needed to support the recovery procedures. These goals are accomplished by relying on algebraic methods of constructing the data encoding procedures as well as on novel algorithms of data exchange and recovery. Overall the research performed in the course of this project contributes to the development of more efficient data management procedures in large-scale distributed storage systems.This project puts forward new algebraic procedures for data encoding and recovery that enables one to achieve tradeoff between overhead and repair bandwidth based on the concept of local recovery. The project studies both the case of recovering from a single disk loss, which is the most frequent problem in systems, as well as from the failure of multiple disks, addressing the problem of correcting one erasure as well as multiple erasures in data encoding. New bounds on the distance of codes with the locality requirement derived in this research are attained with new constructions of optimal locally recoverable codes equipped with simple recovery procedures. The project also addresses the problem of simultaneous recovery of data from multiple locations, enhancing data availability in large-scale distributed storage systems which are a key backbone component of the 21st century economy.