最大可恢复性：编码理论的交汇点

《IEEE BITS the Information Theory Magazine》：Maximal Recoverability: A Nexus of Coding Theory

本文综述了最大可恢复性（MR）码两大分支：局部可恢复码（LRCs）与网格码（GCs），探讨其核心可恢复性保证及最优构造方法，并揭示与skew多项式码、高阶MDS码及图结构刚性的深层关联。

　　

摘要：

在现代大规模计算系统中，纠错码的一个关键用途是巧妙地引入冗余以确保在发生故障时能够恢复数据。为了充分利用每一字节的数据，实践者和理论家们提出了最大恢复性（MR）框架，以研究各种架构中的最优纠错码。在这篇综述中，我们深入研究了两种MR码：局部可恢复码（LRCs，也称为部分MDS码）和网格码（GCs）。对于这两类码，我们讨论了每种码的主要恢复性保证，以及目前已知的最优编码方法。在此过程中，我们还探讨了MR码与计算机科学和数学中许多其他问题之间的有趣联系。对于MR LRCs，斜多项式码的使用统一了许多之前的编码方法；对于MR GCs，高阶MDS码的理论表明MR GCs可以用来构建最优的列表可解码码。此外，MR GCs的最优恢复模式与图的结构刚性这一长期存在的问题密切相关。