Codes with unequal locality
Codes with unequal locality
复制标题
DOI：
10.1109/isit.2016.7541336
复制
发表时间：
2016-01
期刊：
影响因子：
--
通讯作者：
S. Kadhe;A. Sprintson
中科院分区：
文献类型：
--
作者：
S. Kadhe;A. Sprintson
在许多实际环境中，需要设计具有一定局部性约束的分布式存储代码。对于码C，如果它的第i个符号可以通过访问C的其他r个符号来恢复，则称其第i个符号具有局部性。局部可修复码(LRC)是使得每个符号都具有小局部性的码族。在本文中，我们主要研究符号局部性不同的LRC，其中码的不同符号具有不同的局部性。首先，我们考虑了一类具有不等信息局部性的码，即只对信息符号施加不等局部性约束的系统码。对于这类码，我们计算了作为局部性约束的函数的最小距离的一个紧上界。我们证明了Huang等人构造的金字塔码.可适用于设计具有不等信息局部性的最优码，从而达到最小距离界。接下来，我们考虑具有不等全符号局部性的码，即对所有符号施加局部性约束的码。我们建立了最小距离的一个上界，作为每个局部值的符号数目的函数。我们证明了Silberstein等人基于秩度量码的构造。可以适用于获得具有不等全符号局部性的最优码。最后，我们引入了代码的局部性要求的概念，它可以被看作是对符号的可恢复性要求。代码的信息局部性要求实质上规定了必须出现在代码中的每个局部值的信息符号的最小数目。对于给定的局部性要求，我们提出了一个贪婪算法来构造在满足局部性要求的所有码中具有最小距离的码。
In many practical settings, there is a need to design distributed storage codes with certain locality constraints. For a code C, its i-th symbol is said to have locality r if it can be recovered by accessing some other r symbols of C. Locally repairable codes (LRCs) are the family of codes such that every symbol has small locality. In this paper, we focus on LRCs with unequal symbol locality, wherein different symbols of the code have different locality values. First, we consider a class of codes with unequal information locality, i.e., systematic codes with unequal locality constraints imposed only on the information symbols. For this class of codes, we compute a tight upper bound on the minimum distance as a function of locality constraints. We demonstrate that the construction of Pyramid codes by Huang et al. can be adapted to design optimal codes with unequal information locality that achieve the minimum distance bound. Next, we consider codes with unequal all-symbol locality, i.e., codes in which the locality constraints are imposed on all symbols. We establish an upper bound on the minimum distance as a function of number of symbols of each locality value. We show that the construction based on rank-metric codes by Silberstein et al. can be adapted to obtain optimal codes with unequal all-symbol locality. Finally, we introduce the concept of locality requirement of a code, which can be viewed as a recoverability requirement on symbols. Information locality requirement of a code essentially specifies the minimum number of information symbols of each locality value that must be present in the code. For a given locality requirement, we present a greedy algorithm to construct codes that have maximum minimum distance among all codes that satisfy the locality requirement.