分布式存储系统中局部修复码的研究

Recently, the locally repairable code (LRC) becomes a hot topic in the field of coding for distributed storage. Binary LRC and t-LRC are two kinds of LRCs which have good potential applications, and attract lots of attention. This project will carry out a research on some open problems in binary LRCs and t-LRCs.. For binary LRCs, we focus on the problem of determining its optimal minimum distance. On the one hand, we will give a tight bound on the minimum distance by making a deep study on its locality property; On the other hand, we will construct binary LRC with optimal minimum distance via some different approaches.. For t-LRCs, we focus on codes with optimal minimum distance or optimal information rate. On the one hand, we will establish general frameworks which connect the locality property and minimum distance, or connect the locality property and information rate. Then we will derive new upper bound on the minimum distance or information rate by using these frameworks. On the other hand, we will find new methods to construct t-LRCs.

局部修复码是近年来分布式存储编码领域中的研究热点。其中二元局部修复码和可并行的局部修复码由于其良好的应用潜力，更是受到了广泛关注。本项目将针对二元局部修复码和可并行的局部修复码中一些亟待解决的问题开展研究：. 在二元局部修复码方面，本项目着力于解决其最优极小距离这个公开问题。一方面，我们将通过深入考察其局部修复性的特点，对二元局部修复码给出紧的极小距离上界；另一方面，我们将利用各种工具，构造极小距离达到最优的二元局部修复码。. 在可并行的局部修复码方面，本项目关注其最优极小距离和最优信息率这两个问题。一方面，我们将构建联系其局部修复性与极小距离、局部修复性与信息率之间的理论框架，并利用这些框架给出更好的极小距离及信息率上界；另一方面，我们将寻找构造可并行的局部修复码的新方法。

近年来，局部修复码因其在大规模分布式存储系统中的应用潜力受到了越来越多的关注。一个[n,k,d]线性码被称作有局部性r的局部修复码如果其任意一个位置的值都能够通过读取其它不超过r个位置来恢复。当应用到实际分布式存储系统中时，局部性r小的局部修复码支持错误节点的高效修复，因而受到了极大的关注。此外，信息位k的个数决定了系统的存储效率，极小距离d的大小决定了系统的整体容错性能，而二元码能够提高系统的编码和更新效率。因此二元局部修复码的最优极小距离问题和最优局部修复码的设计问题一直是分布式存储编码领域的研究热点。本项目在二元局部修复码局部性和极小距离之间的制约关系以及二元局部修复码的构造两个方面开展研究，取得了如下结果。1）针对具有不相交局部修复结构的二元局部修复码，首次给出了其堆球界；2）针对具有一般局部修复结构的二元局部修复码，将其最优极小距离问题转化为一个优化问题，并给出了一个隐式的上界；3）针对具有一般局部修复结构的二元局部修复码得两类特殊参数情况，通过解对应优化问题给出了形式简单的显式上界；4）给出了一种新的局部修复码的构造方法，并由此构造出了最优的二元局部修复码；5）对线性局部修复码给出了一种Shortening技巧，并由此在小码长情形下得到了一大类最优或几乎最优的局部修复码。