论文部分内容阅读
在大规模分布式存储系统中，局部修复码能够有效降低系统修复失效节点的复杂度，因而广受关注。其中极小距离较大的局部修复码能够保证系统有较高的整体容错能力，故更具应用价值。本文对三种典型的局部修复性，即局部性r、局部性(r，δ)和局部性(r，δ)c，讨论了相应码的极小距离上界以及达到最优极小距离的码的构造等问题。具体的，本文包含了以下内容: 首先，我们介绍了线性码的局部性r和局部性(r，δ)的概念以及前人得到的极小距离上界，并归纳了这些上界的不同证明方法。我们引入了再生集的概念，并在再生集的框架下考察了一般情形下的局部性r和局部性(r，δ)。事实上，利用再生集我们可以建立局部性与极小距离之间的一般联系，并由此对前人的多种局部性要求下的极小距离上界给出统一形式的证明。 其次，我们对满足任意位局部性r的[n，k]线性码考察了其能够达到的最大极小距离，这里任意位局部性r是指码的每一位都是其它某r位的一个线性组合。我们首先给出了一个基于整数规划问题的极小距离上界。然后通过求解这个整数规划问题，在n1＞n2的情况下得到了一个显式的极小距离上界，这里n1=n/r+1，n2=n1(r+1)-n。最后，利用线性化多项式在n1＞n2时构造了一个达到此上界的线性码。事实上基于这些结果，我们完全确定了r≤√n-1的情形下满足任意位局部性r的线性码所能达到的最大极小距离，而r≤√n-1是极具应用价值的参数情形。 最后，我们提出局部性(r，δ)c，为码字的一位提供δ-1个互不相交的局部修复组，其中每个局部修复组包含至多r个其它位。这种局部性允许对一个位上的值做并行的访问，在热数据的存储中十分重要。对满足信息位局部性(r，δ)c的[n，k]线性码，我们给出了一个极小距离上界并证明了在n≥k(r(δ-1)+1)时总存在达到此上界的码。而对于满足任意位局部性(r，δ)c的码，我们构造了一类有较好极小距离的线性码（即方格码）和一类有较高信息率的二元码。