Error Decoding of Locally Repairable and Partial MDS Codes

Lukas Holzbaur, Sven Puchinger, Antonia Wachter-Zeh

Abstract

Locally repairable codes (LRCs) and partial maximum distance separable (PMDS) codes are essential for modern distributed storage systems. While traditionally optimized for erasure recovery, these codes often encounter silent data corruption or synchronization errors. This work demonstrates that by utilizing interleaved decoding, the error-correction radius of LRCs and PMDS codes can be extended beyond the classical minimum distance bound. We analyze the asymptotic behavior of these codes and show that for large-scale systems, the probability of successful decoding approaches unity even when the number of errors significantly exceeds the standard $d/2$ limit.

Introduction

In cloud storage environments, data is distributed across multiple servers to ensure reliability. Erasure coding is the standard approach for handling server failures. However, "errors"—where data is corrupted without a known location—pose a more significant challenge. Standard unique decoding is limited by the code's minimum distance $d$, typically correcting only up to $d/2$ errors.

This research addresses the challenge of decoding beyond this theoretical limit. The authors exploit the physical reality of data centers: a faulty server often causes "burst errors," affecting the same relative position across multiple independent codewords stored on that server. By treating these codewords collectively through interleaving, the system's resilience can be dramatically improved without changing the underlying storage infrastructure.

Methodology: Interleaved Decoding

The core technique proposed is Interleaved Decoding. Instead of decoding codewords in isolation, multiple codewords are arranged into a matrix. If a server fails or corrupts data, it affects an entire column of this matrix.

Illustration of interleaved codewords across local groups with burst errors affecting columns.

Interleaved Supercode Decoding for LRCs

For Tamo-Barg LRCs, which are subcodes of Reed-Solomon (RS) codes, the authors apply an interleaved RS decoder to the "supercode." This allows for correcting errors far beyond the $d/2$ limit by leveraging the local parity structures and the properties of the larger RS code.

Decoding PMDS Codes

For PMDS codes, the authors utilize the Metzner-Kapturowski algorithm, a generic $O(n^3)$ complexity approach. The paper provides a rigorous mathematical proof that for PMDS codes, the conditions for this algorithm's success—specifically a property termed $(t+1)$-independence—are almost always satisfied as the code length $n$ increases.

Key Insights and Results

The Advantage of Burst Errors

While burst errors are typically seen as a liability, their structured nature is a "feature" in the context of interleaved decoding. Because the errors are aligned across the interleaving order $\ell$, the decoder can identify the error locations more effectively. In practical systems with 512-byte sectors, $\ell$ is naturally high, facilitating high success rates.

Extended Decoding Radius

The research shows that for interleaved Tamo-Barg codes, the decoding radius increases to approximately $t_{max} \approx \frac{\ell}{\ell+1}(d-1)$. For PMDS codes, the gains are even more striking. In a sample PMDS code with $d=7$ (normally correcting 3 errors), interleaved decoding successfully corrected 6 errors with high probability.

Asymptotic Reliability

A critical result of this work is the proof of asymptotic reliability. As the code length $n$ grows, the probability of failing to decode up to $n-k-1$ errors vanishes. In one evaluated scenario, the failure probability was calculated to be less than $10^{-1223}$, rendering the system effectively immune to such error patterns in practical applications.

Conclusion and Future Work

This work provides a software-only path to significantly enhancing the reliability of distributed storage. By shifting from independent to interleaved decoding, systems can recover from corruption levels that were previously considered fatal. Future research may focus on the impact of adversarial (non-random) error patterns and optimizing field size requirements to reduce computational overhead in hardware implementations.

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},
}
Figure