Locally Repairable Convolutional Codes with Sliding Window Repair

摘要

Locally repairable convolutional codes (LRCCs) for distributed storage systems (DSSs) are introduced in this work. They enable local repair, for a single node erasure, and slidingwindow global repair, which can correct up to ${ext{d}}_j^c - 1$ node erasures in a window of j+1 consecutive blocks of n nodes, where ${ext{d}}_j^c$ is the jth column distance of the code. The parameter j can be adjusted, for a fixed LRCC, according to different catastrophic erasure patterns, requiring only to contact $nleft( {j + 1} ight) - {ext{d}}_j^c + 1$ nodes, plus less than μn other nodes, in the storage system, where μ is the memory of the code. A Singleton-type bound is provided for ${ext{d}}_j^c$. If it attains such a bound, an LRCC can correct the same number of catastrophic erasures in a window of length n(j +1) as an optimal locally repairable block code of the same rate and locality, and with block length n(j +1), but being able to perform the flexible and somehow local sliding-window repair by adjusting j. Furthermore, by sliding the window to consider previous or consequent nodes without erasures, or by increasing the window size, the LRCC can potentially correct more erasures in the original window of n(j + 1) nodes than the optimal locally repairable block code. Finally, an explicit construction of LRCCs whose column distances attain the provided Singletontype bound, up to certain parameter j = L, is obtained based on known maximum sum-rank distance convolutional codes.