Guodong Li（研究生会员，IEEE）、Ningning Wang、Sihuang Hu（会员，IEEE）和Min Ye等作者在2024年11月的《IEEE Transactions on Information Theory》（第70卷第11期）上发表了一项关于最小存储再生（Minimum Storage Regenerating, MSR）码的重要研究。这项研究由山东大学密码技术与信息安全教育部重点实验室、山东大学网络科学与技术学院以及美国IonQ公司合作完成，并得到了中国国家重点研发计划、国家自然科学基金和山东省泰山学者计划的支持。论文的标题为《MSR Codes with Linear Field Size and Smallest Sub-packetization for Any Number of Helper Nodes》，聚焦于分布式存储系统中高效修复单节点故障的编码构造问题。

学术背景

分布式存储系统广泛采用最大距离可分（Maximum Distance Separable, MDS）码以实现最优容错能力。然而，传统MDS码（如Reed-Solomon码）在修复故障节点时需下载大量数据，导致修复带宽（repair bandwidth）过高。Dimakis等人提出修复带宽的理论下限，并定义了MSR码——一类满足该下限的MDS阵列码。MSR码的核心挑战在于平衡三个参数：子分组化（sub-packetization）等级ℓ、有限域大小q和修复度（repair degree）d。此前的研究虽已实现ℓ的理论下限（ℓ ≥ s⌈n/s⌉，其中s = d − k + 1），但仅能在指数级域大小或有限d值（如d ∈ {k+1, k+2, k+3}或d = n−1）下构造最优访问（optimal-access）MSR码。本文旨在突破这一限制，为所有d ∈ [k+1, n−1]设计ℓ和q均最优的MSR码。

研究方法与流程

1. 编码构造框架

研究采用(n, k, ℓ)阵列码的校验方程形式：
[ C = {(c0, \ldots, c{n-1}) : H_0c0 + \cdots + H{n-1}c_{n-1} = 0} ]
其中，每个节点( c_i )是域( \mathbb{F}_q^\ell )中的向量，校验矩阵( H_i )为( r\ell \times \ell )矩阵。MDS属性要求任意r个节点的校验子矩阵行列式非零（全局约束）。为降低q的复杂度，作者将全局约束分解为( O_s(n) )个局部（组内）约束，通过精心设计( H_i )的递归结构实现。

2. 核矩阵与分组设计

• 核矩阵（Kernel Maps）：定义s+1个核映射( K_b^{(t)}(x[s]) )，生成具有特定分块结构的矩阵（如式(4)所示），其非零块位于主对角线或第b行。
  
• 分组策略：将n个节点分为( \lceil n/s \rceil )组（最优访问码）或( \lceil n/(s+1) \rceil )组（非最优访问码），每组分别设计校验矩阵。例如，最优访问码的校验矩阵( H{as+b} = M{a,b}^{®} )，其中( M_{a,b}^{®} )通过张量积和分块操作构建（式(16)）。
  

3. 局部约束与域大小优化

通过选择满足局部非零行列式条件（式(14)-(15)）的ns个域元素( \lambda_i )，确保MDS属性。作者证明：
- 存在性（Lemma 6）：当( q \geq ns + (s-1)2^{s-2} )时，可在( O_s(n) )时间内找到所需( \lambda_i )。
- 显式构造（Lemma 7）：在扩域( \mathbb{F}_p[\alpha] )中，取( \lambda_i = \alpha^i )即可满足条件（( q > \max{ns, p^{s^5}} )）。

4. 修复方案

• 最优访问码：故障节点( c{as+b} )通过下载其他d节点的1/s数据（通过修复矩阵( R{a,b} )选择特定行）实现修复，满足割集界（cut-set bound）。
  
• 非最优访问码：最后一组节点修复需额外访问组内部分数据，牺牲最优访问性以换取更小的ℓ（( \ell = s\lceil n/(s+1) \rceil )）。
  

主要结果

1. 理论突破：首次构造了对所有d ∈ [k+1, n−1]的显式最优访问MSR码，其ℓ = s⌈n/s⌉达到理论下限，且q = O_s(n)（解决Open Problem 1）。
   
2. 次优构造：提出ℓ = s⌈n/(s+1)⌉的非最优访问码，显著推进Open Problem 2的解决。
   
3. 技术核心：通过递归核矩阵设计，将全局约束局部化，并利用置换矩阵（Lemma 1）统一不同分组的校验结构。
   

结论与价值

本研究在MSR码的理论与实用化之间架设了桥梁：
- 科学价值：为高码率MSR码提供了首个线性域大小的通用构造，解决了领域内长期存在的开放性问题。
- 应用价值：小域大小和低子分组化降低了存储系统的实现复杂度，尤其适合固定冗余度（r = n−k）的大规模分布式场景。

亮点与创新

1. 方法论创新：通过“核矩阵膨胀”技术（Blow-up Technique）将复杂全局问题分解为可管理的局部约束。
   
2. 参数最优性：同时优化ℓ和q，填补了d = k+3至n−2之间的构造空白。
   
3. 修复效率：最优访问码支持常数修复（constant repair），显著提升实际系统性能。
   

其他贡献

论文附录详细证明了核矩阵的可逆性（Corollary 1）和修复方案的MDS保持性（Lemma 3），并通过具体示例（如n=6, k=2, d=4）验证了构造的正确性。此外，作者对比了与Vajha等人构造的异同，指出其核矩阵元素复用策略的局限性，为后续研究提供了改进方向。

这项研究为分布式存储编码领域树立了新的标杆，其技术框架有望拓展至协作修复或机架感知（rack-aware）MSR码的设计中。