On the Locality of Codeword Symbols

By Parikshit Gopalan, Cheng Huang, Huseyin Simitci, Sergey Yekhanin. IEEE Transactions on Information Theory, 2011

847 citations recorded by the source corpus.

Consider a linear [n,k,d]q code C. We say that the ith 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 strong for small distances. This gives a fairly complete picture of the tradeoffs between codewords length, worst case distance, and locality of information symbols. We then consider the locality of parity check symbols and erasure correction beyond worst case distance for optimal codes. Using our structure theorem, we obtain a tight bound for the locality of parity symbols possible in such codes for a broad class of parameter settings. We prove that there is a tradeoff between having good locality and the ability to correct erasures beyond the minimum distance.

Subfields: Artificial Intelligence, Computer Networks and Communications, Molecular Biology

View Paper: https://www.semanticscholar.org/paper/400a0ea983ab9083efd283b98ad0ada348494b15

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Molecular Biology

Citations in the corpus

Optimal linear codes with a local-error-correction property (2012, neutral): “(30) Now, since∀i ∈ [a], |Si| ≤ r + δ − 1, from (30), it follows that|Si| = r + δ − 1 and Si ∩ Sj = φ, 1 ≤ i j ≤ a. (31) Combining (29) and (31), we also get that dim((C⊥)Si) = δ − 1, ∀i ∈ [a].”
Centralized Repair of Multiple Node Failures With Applications to Communication Efficient Secret Sharing (2016, background): “1 In addition, locality, the number of nodes contacted during repair of a single node, is another measure of node repair efficiency which has been extensively studied in the literature [17].”
Locality and Availability in Distributed Storage (2014, background): “Note that for t = 1, the bound in (6) reduces to the distance bound for codes with r-locality [10], [12], i.”
Codes for network switches (2013, positive): “Another similar notion with local-reconstruction property is locally repairable codes [3] [6], where a symbol can be recovered from some (fixed set of) other symbols.”
The Capacity of Private Information Retrieval (2016, background): “tance hiding [15, 16, 17], multiparty computation [18], secret sharing schemes [19, 20] and locally decodable codes [21]. Throughthe connection between locally decodable and locally recoverable codes [22], PIR also connects to distributed data storage repair [23], index coding [2] and the entire umb”
The Capacity of Robust Private Information Retrieval With Colluding Databases (2016, background): “2777490 connections between locally decodable and locally recoverable codes [12], PIR also connects to distributed data storage repair [13] and index coding [14], which in turn encompass all of network coding [15].”
Erasure Coding in Windows Azure Storage (2012, background): “Based on the following theorem, these properties impose a lower bound on the number of parities [21].”
Locally Repairable Codes (2012, methodology): “The set of n local encoding functions f(Y in i ,Y out i ), i ∈ [n], of a capacity achieving scheme on G(n, r, d,α), can be mapped to a code of length n, that encodes a file of size C in n coded symbols, each of size α bits.”
Batch codes through dense graphs without short cycles (2014, background): “This line of work generalizes the literature on locally repairable codes [20]–[24], where one is interested in reconstructing a single code symbol by contacting a small number of other code symbols.”