On a Class of Optimal Locally Recoverable Codes with Availability
Clifton Garrison, Giacomo Micheli, Logan Nott, Vincenzo Pallozzi Lavorante, Phillip Waitkevich · 2023
An [n, k, d, r] Locally Recoverable Code (LRC) is a linear code of dimension k, length n, minimum distance d, and locality r, where the locality is the minimum number of coordinates of a codeword one has to access when recovering a single erasure. In this paper we construct a new family of optimal locally recoverable codes with availability t, i.e. any node has t distinct recovery sets. Our codes, for some sets of parameters, achieve the generalized Singleton bound for Locally Recoverable Codes, i.e. $d \leq n - k - \left\lceil {\frac{k}{r}} \right\rceil + 2$, while still allowing availability of nodes. From an information theoretical perspective, this is possible because the inequalities for the distance that take into account availability simply return the Singleton bound in certain regimes of parameters n, k, r, d, t, even with t ≥ 2. This allows the existence of codes with availability t ≥ 2 that still match the Singleton bound for LRCs mentioned earlier. Our construction relies on a new combinatorial structure, arising from the theory of finite fields, that allows to produce orthogonal partitions by leveraging the arithmetic of polynomial rings.