Optimal Fractional Repetition Codes
Natalia Silberstein, Tuvi Etzion · arXiv (Cornell University) · 2014
Fractional repetition (FR) codes is a family of codes for distributed storage systems that allow for uncoded repair having the minimum repair bandwidth. However, in contrast to minimum bandwidth regenerating codes, where a random set of certain size of available nodes is used for a node repair, the repairs with FR codes are table based. In this work we consider bounds on the fractional repetition capacity. Optimal FR codes which attain these bounds are presented. The constructions of optimal FR codes are based on combinatorial designs and on different families of regular and biregular graphs. Finding optimal codes raises some interesting questions in graph theory. We discuss these questions and their solutions. In addition, we analyze other properties of the constructed codes, allowing parallel independent reads of many subsets of the stored symbols, by showing a connection to combinatorial batch codes. We also define for each code a rate hierarchy which resembles to the well known generalized Hamming weight hierarchy.