Fractional Repetition Codes for Repair in Distributed Storage Systems
arXiv:1010.2551
Abstract
We introduce a new class of exact Minimum-Bandwidth Regenerating (MBR) codes for distributed storage systems, characterized by a low-complexity uncoded repair process that can tolerate multiple node failures. These codes consist of the concatenation of two components: an outer MDS code followed by an inner repetition code. We refer to the inner code as a Fractional Repetition code since it consists of splitting the data of each node into several packets and storing multiple replicas of each on different nodes in the system. Our model for repair is table-based, and thus, differs from the random access model adopted in the literature. We present constructions of Fractional Repetition codes based on regular graphs and Steiner systems for a large set of system parameters. The resulting codes are guaranteed to achieve the storage capacity for random access repair. The considered model motivates a new definition of capacity for distributed storage systems, that we call Fractional Repetition capacity. We provide upper bounds on this capacity while a precise expression remains an open problem.
References in corpus (3)
Cited by in corpus (26)
- Layered, Exact-Repair Regenerating Codes Via Embedded Error Correction and Block Designs
- Capacity and Security of Heterogeneous Distributed Storage Systems
- Optimal Repair of MDS Codes in Distributed Storage via Subspace Interference Alignment
- Codes with Local Regeneration
- Explicit MBR All-Symbol Locality Codes
- Coded Caching with Distributed Storage
- On the Duality and File Size Hierarchy of Fractional Repetition Codes
- The existence of fractional repetition codes
- Non-homogeneous Two-Rack Model for Distributed Storage Systems
- A Piggybacking Design Framework for Read-and Download-efficient Distributed Storage Codes
- When and By How Much Can Helper Node Selection Improve Regenerating Codes?
- Exact-Repair Regenerating Codes Via Layered Erasure Correction and Block Designs
- Analysis and Construction of Functional Regenerating Codes with Uncoded Repair for Distributed Storage Systems
- Storage codes -- coding rate and repair locality
- Optimal Fractional Repetition Codes and Fractional Repetition Batch Codes
- When Can Helper Node Selection Improve Regenerating Codes? Part I: Graph-Based Analysis
- Fractional repetition codes with flexible repair from combinatorial designs
- Space-Time Storage Codes for Wireless Distributed Storage Systems
- Algebraic Codes and a New Physical Layer Transmission Protocol for Wireless Distributed Storage Systems
- Optimal Construction of Regenerating Code through Rate-matching in Hostile Networks
- Novel Repair-by-Transfer Codes and Systematic Exact-MBR Codes with Lower Complexities and Smaller Field Sizes
- Two-layer Locally Repairable Codes for Distributed Storage Systems
- Exact Optimized-cost Repair in Multi-hop Distributed Storage Networks
- Bounds on Fractional Repetition Codes using Hypergraphs
- On Universally Good Flower Codes
- Locality and Availability of Array Codes Constructed from Subspaces