Optimal Locally Repairable Systematic Codes Based on Packings

Han Cai, Minquan Cheng, Cuiling Fan, Xiaohu Tang

TL;DR

This paper bridges the gap between locally repairable codes (LRCs) and combinatorial packings, showing how packings can be used to construct optimal LRCs with flexible parameters. The authors introduce new constructions and characterizations that enable the design of LRCs with improved efficiency for distributed storage systems.

What Problem Does This Paper Address?

Distributed storage systems, like those used by Amazon and Google, store massive amounts of data across many disks. To ensure data availability and fault tolerance, replication or erasure codes are used. While simple replication is straightforward, it incurs significant storage overhead. Erasure codes, particularly Maximum Distance Separable (MDS) codes, offer better efficiency but require accessing many data blocks to recover a single lost block, which is inefficient in large-scale systems.

Locally Repairable Codes (LRCs) were introduced to address this by allowing a lost data block to be recovered by accessing only a small subset of other blocks. This paper focuses on a specific type of LRC that has "multiple disjoint repair groups" for each information symbol, which offers good parallel reading capabilities and can achieve higher code rates. The challenge is to construct optimal LRCs with these desirable properties, meaning they meet theoretical bounds on minimum distance and have efficient repair mechanisms. Existing constructions are often limited in their parameters or rely on complex combinatorial structures.

Methods

The paper's core contribution is establishing a combinatorial link between LRCs and packings. Packings are a well-studied combinatorial structure that can be thought of as a collection of subsets (blocks) of a set of elements, with constraints on how elements appear together in blocks.

The authors propose:

  • Combinatorial Characterization: They show that the properties of LRCs, particularly their repair groups, can be directly mapped to the structure of packings. Specifically, the supports of partial check columns in a systematic code's generator matrix form a packing.
  • Constructions based on Packings:
    • Construction A: This construction uses a (k, R, 1) packing to generate an optimal LRC. It's a generalization of existing methods and allows for flexible parameter choices.
  • Construction B: This construction leverages resolvable packings and existing MDS codes to build LRCs. It's a generalization of the "Pyramid Code" and offers a way to construct LRCs with specific locality and update-efficiency properties.
  • Analysis of Optimality: The paper provides conditions under which these constructions yield optimal LRCs, both in terms of minimum distance and update-efficiency. They analyze the relationship between packing parameters and LRC properties.

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions and combinatorial properties rather than empirical evaluation on datasets.

Key Insights and Ideas

  • Packings as the Key: The paper reveals that packings are not just a tool for analysis but a fundamental building block for constructing optimal LRCs. This provides a unified framework for understanding and designing these codes.
  • Flexibility through Packings: By using different types of packings (regular, resolvable), the authors can generate LRCs with a wide range of parameters, overcoming limitations of previous construction methods.
  • Trade-offs: The paper highlights the inherent trade-offs between code rate, locality, and parallel reading ability. Higher locality (more repair groups) can lead to lower code rates, and the choice of packing parameters influences this balance.
  • Generalization: Construction A generalizes existing methods for constructing LRCs from combinatorial designs, and Construction B generalizes the Pyramid Code, offering broader applicability.

Key Results

  • Characterization Theorem: Theorem 1 establishes an "if and only if" condition relating LRCs to packings, providing a powerful theoretical tool.
  • Optimal Constructions: Constructions A and B are presented, which, when combined with specific types of packings, yield optimal LRCs with desired properties (e.g., optimal distance, optimal update-efficiency).
  • Conditions for Optimality: The paper derives necessary and sufficient conditions for a code to be optimal, based on the properties of the underlying packing.
  • Example Demonstrations: Several examples are provided, including a specific construction (Example 3) and a table (Table I) showcasing known packings and the resulting optimal LRCs, demonstrating the practical applicability of the theory.

Limitations and Future Work

  • Existence of Packings: While the paper shows how packings can be used to construct LRCs, the existence and construction of suitable packings with specific parameters remain a challenge in combinatorial design theory. The authors encourage further research into constructing such packings.
  • Parameter Space: The paper focuses on specific types of LRCs and packings. Exploring a broader range of LRC definitions and packing variations could lead to new discoveries.
  • Practical Implementation: While the theoretical framework is strong, translating these constructions into highly efficient and practical storage system implementations would require further engineering effort.

The authors explicitly invite further research into constructing new packings and resolvable packings, as this will directly lead to the discovery of more optimal locally repairable codes.

Summary updated

Abstract

Locally repairable codes are desirable for distributed storage systems to improve the repair efficiency. In this paper, a connection between locally repairable codes with multiple disjoint repair sets and packings is derived under the condition that each repair set contains exactly one check symbol. Particularly, conditions under which an optimal locally repairable code corresponds to a packing are also characterized. As an application of this connection, some optimal locally repairable codes can be obtained by packings. Specifically, two constructions of locally repairable codes are proposed which not only generalize some known explicit constructions but also give optimal locally repairable codes with flexible new parameters.
BibTeX
@article{cai2019optimal,
  author = {Han Cai and Minquan Cheng and Cuiling Fan and Xiaohu Tang},
  title = {{Optimal Locally Repairable Systematic Codes Based on Packings}},
  journal = {IEEE Trans. Communications},
  year = {2019},
  doi = {10.1109/tcomm.2018.2869800},
}
Figure