Error Decoding of Locally Repairable and Partial MDS Codes

Lukas Holzbaur, Sven Puchinger, Antonia Wachter-Zeh

TL;DR

This paper demonstrates how to push the error-correction limits of distributed storage codes—specifically Locally Repairable Codes (LRCs) and Partial MDS (PMDS) codes—beyond their theoretical minimum distance. By using interleaved decoding, the authors show that we can correct significantly more errors than standard methods allow, with a success probability that approaches 1 as the system scales.

What Problem Does This Paper Address?

In the world of cloud storage, data is spread across many servers using specialized codes. Usually, these systems are designed to handle erasures (when we know a server is down). However, they also face errors—situations where data is corrupted, but we don't know which server is at fault (e.g., due to synchronization issues or faulty hardware).

Standard decoding techniques are limited by the "minimum distance" of the code; they can generally only correct up to $d/2$ errors. This paper tackles the challenge of decoding beyond that limit. The authors exploit a common reality in data centers: a single faulty server often corrupts the same relative position across many different codewords stored on it (a "burst error"). By looking at these codewords together rather than in isolation, can we build a more resilient system?

Methods

The authors employ Interleaved Decoding, a technique where multiple codewords are treated as a single matrix. If an error occurs at a specific server, it affects an entire column of this matrix.

  1. Interleaved Supercode Decoding: For Tamo-Barg LRCs (a popular class of storage codes), the authors leverage the fact that these are subcodes of Reed-Solomon codes. They apply an interleaved Reed-Solomon decoder to the "supercode," which allows them to correct errors far beyond the standard $d/2$ limit.
  2. Metzner-Kapturowski Algorithm: For PMDS codes, the authors use this generic, low-complexity algorithm ($O(n^3)$). It doesn't require a specific code structure, making it highly versatile.
  3. Probabilistic Analysis: The core of the paper is a mathematical proof showing that for PMDS codes, the conditions required for this algorithm to succeed are almost always met as the code length ($n$) grows.

Datasets

Not discussed in the paper. As a theoretical contribution to coding theory, the paper relies on mathematical proofs, lemmas, and illustrative numerical examples rather than empirical datasets or benchmarks.

Key Insights and Ideas

  • Burst Errors are a Feature, Not a Bug: While burst errors sound bad, their structured nature (affecting the same position across multiple codewords) actually makes interleaved decoding highly effective. In a real storage system with 512-byte sectors, the "interleaving order" is naturally very high, which is exactly what these algorithms need to succeed.
  • The Subcode Advantage: Tamo-Barg codes "inherit" the powerful decoding capabilities of Reed-Solomon codes. This means we can use well-studied RS decoders to protect LRCs.
  • $(t+1)$-Independence: The authors define a property for PMDS codes called $(t+1)$-independence. They prove that as the system scales, almost every possible error pattern satisfies this property, allowing for successful decoding even when the number of errors is nearly as large as the number of redundancy symbols ($n-k-1$).
  • Zero Infrastructure Cost: One of the most practical insights is that these improvements can be implemented purely in software. You don't need to change how data is stored on the disks; you just change how you decode it when errors occur.

Key Results

  • Extended Radius: For interleaved Tamo-Barg codes, the decoding radius increases to $t_{max} \approx \frac{\ell}{\ell+1}(d-1)$, where $\ell$ is the number of interleaved codewords.
  • High Success Probability: For a sample PMDS code with a distance of $d=7$ (which normally corrects only 3 errors), the authors show that interleaved decoding can correct 6 errors with a success probability of approximately $125/143$.
  • Asymptotic Reliability: The paper proves that for PMDS codes, the probability of failing to decode up to $n-k-1$ errors goes to zero as the code length $n$ goes to infinity. In one specific example, the failure probability was calculated to be less than $10^{-1223}$—effectively zero for any practical application.

Limitations and Future Work

  • Random vs. Adversarial Errors: The high success probabilities rely on the assumption that errors are somewhat random or occur in "bursts." If a malicious actor (an adversary) specifically chooses which positions to corrupt to minimize the rank of the error matrix, these probabilistic gains may vanish.
  • Field Size Requirements: Some of the proofs for PMDS codes assume that the field size ($q$) grows along with the code length. While common in coding theory, very large field sizes can increase computational overhead in practice.
  • Interleaving Order: The most dramatic gains require a high interleaving order ($\ell$). While this is natural for large disk sectors, it might not apply to systems dealing with very small, isolated packets of data.

Summary updated

Abstract

In this work it is shown that locally repairable codes (LRCs) can be list-decoded efficiently beyond the Johnson radius for a large range of parameters by utilizing the local error-correction capabilities. The corresponding decoding radius is derived and the asymptotic behavior is analyzed. A general list-decoding algorithm for LRCs that achieves this radius is proposed along with an explicit realization for LRCs that are subcodes of Reed-Solomon codes (such as, e.g., Tamo-Barg LRCs). Further, a probabilistic algorithm of low complexity for unique decoding of LRCs is given and its success probability is analyzed. The second part of this work considers error decoding of LRCs and partial maximum distance separable (PMDS) codes through interleaved decoding. For a specific class of LRCs the success probability of interleaved decoding is investigated. For PMDS codes, it is shown that there is a wide range of parameters for which interleaved decoding can increase their decoding radius beyond the minimum distance such that the probability of successful decoding approaches 1 when the code length goes to infinity.
BibTeX
@article{holzbaur2021error,
  author = {Lukas Holzbaur and Sven Puchinger and Antonia Wachter-Zeh},
  title = {{Error Decoding of Locally Repairable and Partial MDS Codes}},
  journal = {IEEE Trans. Information Theory},
  year = {2021},
  url = {https://openreview.net/forum?id=NdLWCLul-Vb},
}

Loading related content...

Figure