On the Locality of Codeword Symbols

Consider a linear [ n , k , d ] q code C . We say that the i th coordinate of C has locality r , if the value at this coordinate can be recovered from accessing some other r coordinates of C . Data storage applications require codes with small redundancy, low locality for information coordinates, large distance, and low locality for parity coordinates. In this paper, we carry out an in-depth study of the relations between these parameters. We establish a tight bound for the redundancy n - k in terms of the message length, the distance, and the locality of information coordinates. We refer to codes attaining the bound as optimal. We prove some structure theorems about optimal codes, which are particularly…