New bounds and generalizations of locally recoverable codes with availability

Stanislav Kruglik, Kamilla Nazirkhanova, Alexey Frolov

    Research output: Contribution to journalArticlepeer-review

    12 Citations (Scopus)

    Abstract

    We investigate the distance properties of linear locally recoverable codes (LRC codes) with all-symbol locality and availability. New upper and lower bounds on the minimum distance of such codes are derived. The upper bound is based on the shortening method and generalized Hamming weights that are fundamental parameters of any linear codes with many useful applications. This bound improves existing upper bounds. To reduce the gap in between upper and lower bounds, we do not restrict the alphabet size and propose explicit constructions of codes with locality and availability via rank-metric codes. The first construction relies on expander graphs and is better in low rate region. The second construction utilizes the LRC codes developed by Wang et al. as inner codes and is better in high rate region. We also suggest one possible generalization of LRC codes in which the recovering sets can intersect in a small number of coordinates. This feature allows us to increase the achievable code rate and still meet load balancing requirements. We derive upper and lower bounds on the parameters of such codes and present explicit constructions of codes with such a property.

    Original languageEnglish
    Article number8635485
    Pages (from-to)4156-4166
    Number of pages11
    JournalIEEE Transactions on Information Theory
    Volume65
    Issue number7
    DOIs
    Publication statusPublished - Jul 2019

    Keywords

    • Availability
    • codes
    • data storage systems
    • distributed information systems
    • fault tolerance
    • Hamming distance

    Fingerprint

    Dive into the research topics of 'New bounds and generalizations of locally recoverable codes with availability'. Together they form a unique fingerprint.

    Cite this