Computing sharp recovery structures for locally recoverable codes (Q782862)

The reliability of large cloud storage systems traditionally requires distributed block replication over several nodes whose main cost is a large storage overhead. To reduce this cost, efficient codes that allow the repair of lost encoded data using smaller amounts of information are being implemented. Examples of these codes are erasure codes with small locality parameters such as the ones introduced by \textit{P. Gopalan} et al. [IEEE Trans. Inf. Theory 58, No. 11, 6925--6934 (2012; Zbl 1364.94603)], the so-called \(r\)-locally repairable codes (\(r\)-LRC), that is, codes where each of its coordinates can be repaired by accessing at most \(r\) other coordinates. These codes are known to satisfy a Singleton-like bound and codes that meet that bound are called optimal \(r\)-LRC codes. There are several families of optimal \(r\)-LRC codes, however it is not known if these families can be refined to obtain better ones. The main contribution of the paper under review is an algorithm that provides a sharp recovery structure for an arbitrary linear code in terms of minimal codewords of its dual. This algorithm also provides a recovery method, the locality and the dual distance of the given code. The main input of this algorithm is the parity check matrix \(H\) of the given code and Proposition 4 verifies that the algorithm is correct and provides a sharp recovery structure for the given linear code with parity check matrix \(H\). Furthermore, Proposition 5 gives an estimation for the complexity of this algorithm, adapting the proof of Theorem 4.3 of \textit{I. Márquez-Corbella} et al. [Adv. Math. Commun. 10, No. 2, 229--254 (2016; Zbl 1402.94091)]. Several examples illustrate this algorithm and its origin from the theory of Gröbner basis. The last section of the article collects implementations of the author's algorithm for some examples of codes and with corresponding running times for the hardware used.