Fractional Repetition Codes With Flexible Repair From Combinatorial Designs

Oktay Ölmez, Aditya RamamoorthyIEEE Trans. Information Theory 2016 · DOI

TL;DR

This paper introduces a new class of "fractional repetition" (FR) codes for distributed storage systems that offer flexible and efficient data repair. By leveraging combinatorial designs, these codes achieve a desirable balance between storage efficiency, repair bandwidth, and resilience to node failures, outperforming existing methods in certain scenarios.

What Problem Does This Paper Address?

Modern distributed storage systems (DSS) face a critical challenge: ensuring data availability and integrity while efficiently handling node failures. When a storage node fails, it needs to be "regenerated" by downloading data from surviving nodes. Traditional methods like simple replication are storage-inefficient, while standard erasure codes can require significant data downloads for repair, leading to high bandwidth usage and system downtime. Regenerating codes aim to optimize this repair process by minimizing the data downloaded (repair bandwidth) or the storage required per node. However, many existing regenerating codes require complex computations during repair or are inflexible in terms of the number of nodes that need to be contacted for repair. This paper addresses the need for regenerating codes that offer:

  • Exact and uncoded repair: The regenerated node is an exact replica of the failed node, and no complex computations are needed by surviving nodes.
  • Flexible repair: The system can tolerate failures even if the number of nodes contacted for repair is less than the minimum required to reconstruct the entire file (local repair).
  • Combinatorial construction: Building these codes systematically using well-understood mathematical structures.

Methods

The core of this paper lies in constructing Fractional Repetition (FR) codes using various combinatorial designs. FR codes are a specific type of regenerating code that uses "subpacketization," meaning each symbol is spread across multiple nodes. The key techniques include:

  • Combinatorial Designs: The authors leverage structures like Steiner systems, resolvable designs, affine geometries, Hadamard designs, and mutually orthogonal Latin squares (MOLS). These designs provide a systematic way to define how symbols are distributed across storage nodes.
  • Fractional Repetition (FR) Code Definition: A formal definition of FR codes is provided, emphasizing properties like the number of nodes (n), minimum nodes for file recovery (k), repair degree (d), storage capacity per node (a), and repetition degree (p).
  • B-recoverability: A crucial concept defining how a failed node can be regenerated by downloading specific amounts of data (β packets) from a subset of surviving nodes.
  • Kronecker Product: A technique to combine existing FR codes to generate new codes with potentially better parameters, especially for achieving higher values of β (downloading more than one packet per node).
  • Trivial β-expansion: A simple method to increase β by replicating existing codes, which the authors show is often suboptimal compared to their novel constructions.
  • Local Repair Constructions: Developing codes where the repair degree (d) is less than the number of nodes needed for file recovery (k), enabling more flexible and localized repair.
  • Minimum Distance Analysis: Evaluating the resilience of the codes to multiple failures by analyzing their minimum distance, which quantifies the smallest number of node failures that would make the file unrecoverable.

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions and analysis of codes, not empirical evaluation on specific datasets.

Key Insights and Ideas

  • Combinatorial Designs as Building Blocks: The paper powerfully demonstrates how established mathematical structures like Steiner systems and MOLS can be directly translated into efficient distributed storage codes. This bridges theoretical mathematics and practical system design.
  • Flexibility in Repair: The introduction of "local repair" (d < k) is a significant contribution, allowing for more targeted and potentially faster regeneration by contacting fewer nodes than strictly necessary for full file reconstruction.
  • Beyond Trivial Expansion: The authors show that simply replicating existing codes (trivial β-expansion) is not always the optimal way to achieve higher β values. Their constructions using Kronecker products and specific combinatorial designs yield codes with better parameter ranges that cannot be achieved trivially.
  • File Size Determination is Non-Trivial: Accurately calculating the file size (M) that a DSS can support is shown to be complex, depending not just on pairwise overlaps but on the union of symbol sets across k nodes. The paper provides methods to determine this for their constructions.
  • Tradeoffs are Quantified: The paper explicitly analyzes the tradeoffs between failure resilience (pres), code rate (Rc), and minimum distance (dmin), providing insights into how to design codes for specific system requirements.

Key Results

  • New FR Code Families: The paper presents several new families of FR codes derived from various combinatorial designs, offering flexible repair capabilities.
  • Achieving Higher β: Constructions are provided for FR codes with β > 1 that are not trivially obtained from β = 1 codes, enabling more efficient repair bandwidth utilization.
  • Locally Recoverable Codes: The paper introduces and constructs FR codes that support local repair (d < k), achieving optimal minimum distance bounds for certain parameter ranges.
  • Kronecker Product for Code Generation: A systematic method using the Kronecker product is presented to generate new FR codes from existing ones, expanding the range of achievable parameters.
  • File Size Bounds and Optimality: For many of their constructions, the authors determine the exact file size and demonstrate that some codes meet the Singleton bound, indicating their optimality.

Limitations and Future Work

  • Parameter Restrictions: Some constructions have specific parameter requirements (e.g., q being a prime power, specific relationships between parameters).
  • Complexity of File Size Calculation: While methods are provided, determining the file size for general FR codes remains challenging.
  • Future Work:
    • Exploring applications of these codes in other areas of network coding, such as distributed function computation.
  • Investigating other combinatorial designs that might yield desirable FR code properties.
  • Further analysis of code rate, which is related to the expansion properties of bipartite graphs derived from the designs.
  • Developing more general constructions and analysis techniques for FR codes.

Summary updated

BibTeX
@article{olmez2016fractional,
  author = {Oktay Ölmez and Aditya Ramamoorthy},
  title = {{Fractional Repetition Codes With Flexible Repair From Combinatorial Designs}},
  journal = {IEEE Trans. Information Theory},
  year = {2016},
  doi = {10.1109/tit.2016.2531720},
}
Figure