19 Recovering Very Locally: Locally Recoverable Codes
This chapter studies an application-driven direction in coding theory arising from large-scale distributed storage systems, where data is encoded into a codeword \(\)(c_1, c_2, …, c_n) Σ^n\( with the \)i\('th symbol stored on the \)i\(’th server, and server failures correspond to symbol erasures of the codeword. While traditional MDS codes (such as Reed-Solomon codes) give an optimal trade-off between storage overhead and the worst-case number of erasures tolerated, in practice a much more common scenario is that only a \emph{small number} of servers fail, and one wants to repair the failed server(s) \emph{quickly} using few other servers, while still retaining good global distance. \emph{Locally recoverable codes} (LRCs, also called \emph{locally repairable} or \emph{local reconstruction} codes) are designed to achieve exactly this: any codeword symbol can be recovered from few other codeword symbols (locality), while the code retains as large a minimum distance as is compatible with this local constraint. Unlike locally decodable/correctable codes (which recover from a constant fraction of errors but necessarily have vanishing rate), LRCs aim only to recover single (or few) erasures, allowing for small locality \emph{and} high rate simultaneously. \begin{thmenv}[Message symbol locally recoverable code, Def 19.2.1] \label{def:c19-mlrc} Consider a linear code \end{thmenv} \)C ⊆F^n\( of dimension \)k\( where the first \)k\( symbols are information symbols, and the last \)n-k\( are check symbols (i.e., \)C\( is systematic). Such a code is said to be a \)message symbol \(\)(r,d)\(-locally recoverable code\), or \(\)(r,d)\(-mLRC\) for short, if
it has minimum distance at least
\(\)d\(, and \item [(ii)] for every \)i [k]\(, there exists \)R_i ⊆[n] ∖{i}\( of size at most \)r\( such that the \)i\('th symbol \)c_i\( of any codeword \)c = (c_1, c_2, …, c_n) C\( can be recovered from \)c_R_i\( (the restriction of \)c\( to the coordinates in \)R_i\(). \)
A linear code
\(\)C ⊆F^n\( is said to be an \)\(\)(r,d)\(-locally recoverable code\), or \(\)(r,d)\(-LRC\) for short, if
it has minimum distance at least
\(\)d\(, and \item [(ii)] for every \)i [n]\(, there exists \)R_i ⊆[n] ∖{i}\( of size at most \)r\( such that the \)i\('th symbol \)c_i\( of any codeword \)c = (c_1, c_2, …, c_n) C\( can be recovered from \)c_R_i\(. \)
Property (ii) allows local recovery of every codeword symbol (including check symbols), while property (i) protects against more catastrophic large-scale erasures, which must then be handled non-locally. Every \(\)(r,d)\(-LRC is in particular an \)(r,d)\(-mLRC. \)
We restrict attention to codes defined over large fields (of size at least \(\)Ω(n)\(). It turns out that local recovery of only the message symbols is easy to arrange along with optimal distance, as shown by the following construction. \begin{thmenv}[Construction of an optimal mLRC, Thm 19.3.1] \label{thm:c19-mlrc-construction} \uses{def:c19-mlrc} Let \end{thmenv} \)n > k ≥r\( be positive integers and \)q ≥n\( a prime power. Then there is an explicit \)[n,k]\( linear code over \)F_q\( that is an \)(r,d)\(-mLRC where \[ d = n - k - \left\lceil \frac{k}{r} \right\rceil + 2 \, . \] \begin{proof} \uses{def:c19-mlrc, def:c05-mds} We begin with a systematic \end{proof}\)[n_0, k, d]\( MDS code \)C_0\( over \)F_q\( with \)k\( message symbols and \)n_0 - k = d - 1\( parity symbols. This code encodes a message \)x = (x_1, …, x_k) F_q^k\( into \)c F_q^n_0\( where \)c_i = x_i\( for \)1 ≤i ≤k\( (the systematic part), and the check symbols \)c_k+j\( for \)1 ≤j ≤n_0 - k\( are given by \)c_k+j = p^(j), x \( for some \)p^(j) F_q^k\(. That is, the encoding map is \[ \mathbf{x} \mapsto \left( \mathbf{x}, \langle \mathbf{p}^{(1)}, \mathbf{x} \rangle , \langle \mathbf{p}^{(2)}, \mathbf{x} \rangle , \ldots , \langle \mathbf{p}^{(d-1)}, \mathbf{x} \rangle \right) \, . \] Since \)C_0\( is MDS of distance \)d\(, every nonzero codeword has Hamming weight at least \)d\(; in particular, for each \)1 ≤i ≤d-1\(, taking \)x = e_j\( (the \)j\('th standard basis vector, for any \)j [k]\() shows that the codeword \)(e_j, p^(1), e_j, …, p^(d-1), e_j )\( has weight at least \)d\(; since the systematic part already contributes weight \)1\( and there are only \)d-1\( check coordinates in total, every check coordinate must be nonzero on this codeword. Running over all \)j [k]\( shows every coordinate of each \)p^(i)\(, \)1 ≤i ≤d-1\(, is nonzero, i.e. each vector \)p^(i) F_q^k\(, for \)1 ≤i ≤d-1\(, has full support (all \)k\( coordinates nonzero). We now take the last check symbol \)c_n_0\( (corresponding to \)p^(d-1)\() and split it into \)ℓ:= k/r \( symbols, each of which depends on at most \)r\( disjoint message symbols. Formally, partition \)[k] = {1, 2, …, k}\( into sets \)S_1, …, S_ℓ\( where \)S_1, …, S_ℓ- 1\( have size exactly \)r\( (namely \)S_j = {(j-1)r+1, …, jr}\( for \)1 ≤j < ℓ\() and \)S_ℓ= {(ℓ-1)r + 1, …, k}\( has the (at most \)r\() remaining elements of \)[k]\(. For \)1 ≤j ≤ℓ\(, let \)q^(j)\( denote the vector \)p^(d-1)\( zeroed out outside \)S_j\(, so that \)p^(d-1) = ∑_j=1^ℓ q^(j)\( and \)supp(q^(j)) = S_j\( (since \)p^(d-1)\( has full support). Define the new code \)C\( that encodes \)x F_q^k\( into a codeword in \)F_q^n\( for \[ n = k + (d-2) + \ell = k + d - 2 + \left\lceil \frac{k}{r} \right\rceil \] as follows: \[ \mathbf{x} \mapsto \left( \mathbf{x}, \langle \mathbf{p}^{(1)}, \mathbf{x} \rangle , \ldots , \langle \mathbf{p}^{(d-2)}, \mathbf{x} \rangle , \langle \mathbf{q}^{(1)}, \mathbf{x} \rangle , \ldots , \langle \mathbf{q}^{(\ell )}, \mathbf{x} \rangle \right) \, . \] By construction, \)n, k, d, r\( obey the relation \)d = n - k - k/r + 2\( claimed in the theorem. It remains to verify \)C\( is an \)(r,d)\(-mLRC. \textbf{Distance.} For a nonzero \)x\(, comparing the two encodings, the sum of the last \)ℓ\( check symbols of \)C\('s encoding of \)x\( equals the last check symbol \)p^(d-1), x\( of \)C_0\('s encoding, and the remaining \)n_0 - 1\( codeword symbols coincide between the two encodings. Hence the Hamming weight of the \)C\(-encoding of \)x\( is at least the Hamming weight of the \)C_0\(-encoding of \)x\( (any coordinate where the \)C_0\( encoding is nonzero, other than possibly the collapsed last check symbol, remains nonzero in the \)C\( encoding, and if the last \)C_0\( check symbol is nonzero then not all of \)q^(1), …, q^(ℓ)\( vanish on \)x\(). The latter weight is at least \)d\( since \)C_0\( has distance \)d\(. Thus \)C\( has minimum distance at least \)d\(. \textbf{Locality.} Each message symbol \)x_i\( for \)i S_j\( can be recovered from the other message symbols in \)S_j\( together with the check symbol \)q^(j), x \(: indeed \)supp(q^(j)) = S_j\(, so \)q^(j), x= ∑_i’ S_j (q^(j))_i’ x_i’\( is an equation in the unknown \)x_i\( with nonzero coefficient \)(q^(j))_i ≠0\(, and all other terms are known. Since \)|S_j| ≤r\(, every message symbol can be recovered from at most \)r\( other symbols of the codeword. This proves \)C\( is an \)(r,d)\(-mLRC. \)
We now show the distance achieved in Theorem 422 is optimal. The argument does not rely on linearity; it works as long as there are \(\)k\( coordinates on which the code projects bijectively, each of which has a local recovery set of size at most \)r\(. \)
Input: Sets \(\)R_i\( for \)i [k]\(, each of size at most \)r\(, such that for each \)t [k]\(, \)R_t\( contains at least one index outside \)[k]\(. \textbf{Output:} Disjoint sets \)S, T ⊆[n]\( with \)S ⊆[k]\(. \textbf{Procedure:} \begin{enumerate} \item[1.]Initialize \end{enumerate} \)S, T ←∅\(. \item [2.] While \)|S| < (k-1)/r \(, do: \item [3.] \quad Let \)t [k]\( be the minimum element not belonging to \)S ∪T\(. \item [4.] \quad \)S ←S ∪{t}\(. \item [5.] \quad \)T ←T ∪(R_t ∖S)\(. \item [6.] Return \)S, T\(. \)
At each stage of the loop, since each \(\)R_t\( (for \)t [k]\() has size at most \)r\( and contains at least one index outside \)[k]\(, we have \)|R_t ∩[k]| ≤r - 1\(; hence at any stage \)|T ∩[k]| ≤(r-1)|S|\(, so as long as \)|S| < (k-1)/r\( we have \)|S| + |T ∩[k]| ≤r|S| < k - 1\(, which guarantees an index \)t [k]\( outside the current \)S ∪T\( can always be found in Step 3, so the procedure is well defined and terminates. \)
The distance of an
\(\)(r,d)\(-mLRC of length \)n\( and dimension \)k\( must satisfy \[ d \leq n - k - \left\lceil \frac{k}{r} \right\rceil + 2 \, . \] \begin{proof} \uses{def:c19-mlrc, alg:c19-disjoint-st} Let \end{proof}\)C\( be an \)(r,d)\(-mLRC with \)q^k\( codewords over alphabet size \)q\(, and, without loss of generality, that the first \)k\( coordinates are information symbols with local recovery sets \)R_1, …, R_k\(, each of size at most \)r\(; since \)[k]\( is an information set, each \)R_t\( (for \)t [k]\() must include at least one index outside \)[k]\( (otherwise \)c_t\( would be a function of other message symbols alone, contradicting that \)[k]\( freely determines all codewords). Run the procedure of Construction~ \ref{alg:c19-disjoint-st} on \)R_1, …, R_k\( to obtain disjoint sets \)S, T\( with \)S ⊆[k]\(, \)|S| = (k-1)/r \(, and, by construction and induction on the sets added to \)T\(, \)c_T\( determines \)c_S\( for every codeword \)c C\( (since at each step \)t\( is added to \)S\( only after all of \)R_t ∖S\( has been folded into \)T\(, and \)c_t\( is determined by \)c_R_t\(). The final set \)T\( output has size at most \)r (k-1)/r ≤k - 1\(. Since \)c_S\( is determined by \)c_T\(, it is also determined by \)c_[n]∖S\( (as \)T ⊆[n]∖S\(). This implies the projection of \)C\( onto \)[n]∖S\( is injective (one-one), and in particular \)n - |S| ≥k\( (unless \)C\( has distance \)0\(, in which case the bound is trivial). Therefore we may add \)k - 1 - |T|\( further elements of \)[n]∖S\( outside \)S ∪T\( to \)T\(, to obtain a set \)T’\( of size exactly \)k - 1\( with (i) \)T’ ∩S = ∅\(, and (ii) \)c_T’\( determines \)c_S\( (since \)T’ ⊇T\(). Since \)|T’| = k - 1 < k = _q(q^k)\(, by the pigeonhole principle (applied with the \)q^k-1\( possible vectors of length \)|T’|\( as holes and the \)q^k\( codewords, projected onto \)T’\(, as pigeons) there exist two distinct codewords \)c, c’ C\( with \)c_T’ = c’_T’\(. By property (ii), this forces \)c_S = c’_S\( as well. Thus \)c\( and \)c’\( agree on at least \)|T’| + |S| = (k-1) + (k-1)/r \( positions, so the distance of \)C\( is at most \[ n - (k-1) - \left\lfloor \frac{k-1}{r} \right\rfloor \, . \] Using the identity \)(k-1)/r = k/r - 1\( (valid for positive integers \)k, r\(: writing \)k - 1 = qr + s\( with \)0 ≤s < r\(, if \)s = r - 1\( then \)k = (q+1)r\( so both sides equal \)q\(; otherwise \)k = qr + (s+1)\( with \)1 ≤s+1 ≤r-1\( so \)k/r= q+1\(, matching \)(k-1)/r= q\(), we conclude \[ d \leq n - (k - 1) - \left( \left\lceil \frac{k}{r} \right\rceil - 1 \right) = n - k - \left\lceil \frac{k}{r} \right\rceil + 2 \, , \] completing the proof. \)
In Section 19.3 we exhibited an optimal message symbol LRC. We now construct an optimal general (all-symbol) LRC, as a carefully chosen sub-code of a Reed-Solomon code exhibiting locality.
Let
\(\)F_q\( be a finite field, let \)r+1\( divide \)q - 1\(, and let \)1, ω, ω^2, …, ω^r\( be the \)(r+1)\('th roots of unity in \)F_q^*\( (which are all distinct, since the multiplicative group \)F_q^*\( is cyclic of order \)q-1\( and \)r+1 ∣q - 1\(). Then for any \)αF_q\(, \[ \prod _{i=0}^{r} (X - \alpha \omega ^i) = X^{r+1} - \alpha ^{r+1} \, . \] \begin{proof} First take \end{proof}\)α= 1\(. The polynomial \)X^r+1 - 1 F_q[X]\( has degree \)r+1\( and each of \)1, ω, …, ω^r\( is a root of it (as \)(ω^i)^r+1 = (ω^r+1)^i = 1\(), and these \)r+1\( roots are pairwise distinct. Since a nonzero polynomial of degree \)r+1\( over a field has at most \)r+1\( roots, and we have exhibited \)r+1\( distinct roots each with multiplicity at least one summing already to degree \)r+1\(, the factorization \)X^r+1 - 1 = ∏_i=0^r (X - ω^i)\( holds (both sides are monic of degree \)r+1\( with the same roots, counted with multiplicity, so they are equal). For general \)αF_q\(, substitute \)X = αY\(: we get \)(αY)^r+1 - α^r+1 = α^r+1(Y^r+1 - 1) = α^r+1 ∏_i=0^r (Y - ω^i) = ∏_i=0^r (αY - αω^i)\(, i.e. \)X^r+1 - α^r+1 = ∏_i=0^r (X - αω^i)\(, as claimed. \)
Let \(\)n > k ≥r\( be positive integers with \)n\( a multiple of \)r+1\(, and let \)q ≥n+1\( be a prime power such that \)q - 1\( is also divisible by \)r+1\(. Fix \)ωF_q^*\( a primitive \)(r+1)\('th root of unity (which exists since \)F_q^*\( is cyclic of order \)q-1\( and \)r+1 ∣q-1\(). Let \)k’\( be the smallest integer so that \[ k = \left\lceil \frac{k' r}{r+1} \right\rceil \, . \] Consider the Reed-Solomon code over \)F_q\( of dimension \)k’\( and block length \)n := q - 1\(, obtained by evaluating message polynomials \)f F_q[X]\( of degree less than \)k’\( at all of \)F_q^*\(. Define the sub-code \[ C^* = \left\{ \langle f(\alpha ) \rangle _{\alpha \in \mathbb {F}_q^*} \; \middle | \; f(X) = \sum _{i=0}^{k'-1} f_i X^i, \; f_i = 0 \text{ if } i \equiv r \! \! \pmod{r+1} \right\} \, , \] i.e., \)C^*\( consists of the evaluations of those degree-\)(<k’)\( polynomials in which every coefficient \)f_i\( with \)i ≡r r+1\( is forced to be zero. \)
With notation as in Construction 426, the code \(\)C^*\( has dimension exactly \)k\(. \begin{proof} \uses{constr:c19-cstar} Write \end{proof}\)k = k’r/(r+1)\(; this means \)k = (k’r + a)/(r+1)\( for some integer \)a\( with \)0 < a ≤r\( (we cannot have \)a = 0\(, since if \)k = k’r/(r+1)\( were an integer then \)(k’-1)r/(r+1)\( would already equal \)k\(, contradicting minimality of \)k’\(). Inverting for \)k’\(, \[ k' = \frac{(r+1)k - a}{r} = k + \frac{k-a}{r} \, , \] and since \)0 < a ≤r\( one checks \)(k-a)/r = k/r - 1\( (writing \)k = qr + s\( with \)1 ≤s ≤r\( so \)k/r= q+1\(; if \)a ≤s\( then \)(k-a)/r = q + (s-a)/r\( is only an integer when \)a=s\(, giving \)(k-a)/r = q = k/r- 1\(; the divisibility of \)k’\( forces \)a ≡k r\(, i.e. \)a = s\( in this range). Hence \[ k' = k + \left\lceil \frac{k}{r}\right\rceil - 1 \, . \tag {} \]\)*\(\)
Among the coefficients \(\)f_0, …, f_k’-1\(, the ones forced to zero are \)f_r, f_2r+1, f_3r+2, …\(, i.e. every \)(r+1)\('th coefficient starting at index \)r\(; the number of such indices that are at most \)k’ - 1\( equals \)(k’-1-r)/(r+1)+ 1 = k’/(r+1)\(. Therefore the dimension of \)C^*\( (the number of free coefficients) equals \[ k' - \left\lfloor \frac{k'}{r+1}\right\rfloor = \left\lceil \frac{k'r}{r+1}\right\rceil = k \] by the defining relation for \)k’\(. (The evaluation map on \)F_q^*\( is injective on polynomials of degree \)<k’≤q-1\(, so dimension as a vector space of message-coefficient-tuples equals dimension of the code.) \)
With notation as in Construction 426 and \(\)k’\( related to \)k\( as in the proof of Lemma~ \ref{lem:c19-cstar-dimension}, the code \)C^*\( has minimum distance \[ d \geq n - k' + 1 = n - k - \left\lceil \frac{k}{r}\right\rceil + 2 \, . \] \begin{proof} \uses{constr:c19-cstar, def:c05-reed-solomon, lem:c19-cstar-dimension} \end{proof}\)C^*\( is by definition a sub-code of the Reed-Solomon code of dimension \)k’\( and block length \)n = q-1\(, obtained by restricting the message polynomials to a sub-space of the degree-\)(<k’)\( polynomials. A sub-code of a code has distance at least that of the ambient code, so \)d ≥n - k’ + 1\( (the distance of the ambient Reed-Solomon code). Substituting the relation \)k’ = k + k/r- 1\( from the proof of Lemma~ \ref{lem:c19-cstar-dimension} gives \)d ≥n - k - k/r+ 2\(. \)
With notation as in Construction 426, every codeword symbol of \(\)C^*\( has a local recovery set of size \)r\(; that is, \)C^*\( satisfies property (ii) of Definition~ \ref{def:c19-lrc} with locality \)r\(. \begin{proof} \uses{constr:c19-cstar, lem:c19-roots-unity-product} Let \end{proof}\)U = {1, ω, ω^2, …, ω^r}\(, the set of \)(r+1)\('th roots of unity in \)F_q^*\(. Since \)F_q^*\( is cyclic of order \)q - 1\( and \)|U| = r+1\( divides \)q-1\(, the distinct multiplicative cosets \)αU = {α, αω, …, αω^r}\(, for \)α\( ranging over coset representatives, partition \)F_q^*\( into \)(q-1)/(r+1)\( cosets of size \)r+1\( each; it suffices to prove the local recovery property on each individual coset \)αU\(. Fix a codeword symbol location \)αω^i_0 αU\( coming from a polynomial \)f(X) = ∑_i=0^k’-1 f_i X^i\( with \)f_i = 0\( whenever \)i ≡r r+1\( (as in Construction~ \ref{constr:c19-cstar}). Reducing \)f(X)\( modulo \)X^r+1 - α^r+1\( gives a polynomial \)g^(α)(X)\( of degree at most \)r\( that agrees with \)f\( on all of \)αU\( (since each point of \)αU\( is a root of \)X^r+1 - α^r+1\(, by Lemma~ \ref{lem:c19-roots-unity-product} applied with this \)α\(, so \)f(X) ≡g^(α)(X) X^r+1 - α^r+1\( implies \)f\( and \)g^(α)\( take the same values at every root of \)X^r+1-α^r+1\(). Since only the coefficients \)f_i\( with \)i ≡r r+1\( are forced to vanish, and reduction modulo \)X^r+1-α^r+1\( only combines coefficients whose indices are congruent modulo \)r+1\(, the coefficient of \)X^r\( in \)g^(α)(X)\( is (up to a nonzero scalar power of \)α\() a sum of the vanishing coefficients \)f_r, f_2r+1, …\( of \)f\(, and hence is itself \)0\(. Thus \)g^(α)(X)\( has degree at most \)r - 1\( (strictly less than \)r\(). By Lemma~ \ref{lem:c19-roots-unity-product}, the \)r+1\( points of \)αU\( are precisely the roots of \)X^r+1 - α^r+1 = ∏_i=0^r (X - αω^i)\(. A polynomial \)g^(α)\( of degree at most \)r-1\( evaluated at these \)r+1\( distinct points satisfies a single nontrivial linear constraint \)∑_i=0^r λ_αω^i g^(α)(αω^i) = 0\( with all \)λ_αω^i ≠0\(: this is because the \)(r+1)×(r+1)\( Vandermonde-type evaluation matrix at the \)r+1\( points \){αω^i}\( has a \)1\(-dimensional left null space (since evaluation of degree \)≤r-1\( polynomials at \)r+1\( points has rank \)r\(, the space of degree \)≤r\( polynomials), and the coefficient \)λ_αω^i\( corresponding to a given point is (up to scalar) the value at that point of the degree-\)r\( polynomial vanishing at the other \)r\( points of \)αU\(, which is nonzero at \)αω^i\( itself (else it would have \)r+1\( roots while having degree \)r\(). Since \)f(X)\( and \)g^(α)(X)\( agree on \)αU\(, this same linear constraint \)∑_i=0^r λ_αω^i f(αω^i) = 0\( holds among the codeword symbols indexed by \)αU\(, with every coefficient nonzero. In particular, for each \)i_0\(, the codeword symbol at \)αω^i_0\( is recoverable (via this linear equation) from the other \)r\( codeword symbols at \)αU ∖{αω^i_0}\(. As \)αU\( ranges over all cosets partitioning \)F_q^*\(, every codeword location has a local recovery set of size \)r\(, as required. \)
Let
\(\)n > k ≥r\( be positive integers with \)n\( being a multiple of \)r+1\(, and let \)q ≥n+1\( be a prime power such that \)q-1\( is also divisible by \)r+1\(. Then there is an explicit \)[n,k]_q\( code, which is in fact a sub-code of a Reed-Solomon code, that is an \)(r,d)\(-LRC with the optimal distance \[ d = n - k - \left\lceil \frac{k}{r}\right\rceil + 2 \, . \] \begin{proof} \uses{constr:c19-cstar, lem:c19-cstar-dimension, lem:c19-cstar-distance, lem:c19-cstar-locality, thm:c19-singleton-lrc, def:c19-lrc} Let \end{proof}\)C^*\( be the code of Construction~ \ref{constr:c19-cstar}. By Lemma~ \ref{lem:c19-cstar-dimension}, \)C^*\( has dimension \)k\(; by Lemma~ \ref{lem:c19-cstar-distance}, \)C^*\( has distance \)d ≥n - k - k/r+ 2\(; and by Lemma~ \ref{lem:c19-cstar-locality}, every symbol of \)C^*\( has a local recovery set of size \)r\(. Hence \)C^*\( is an \)(r,d)\(-LRC (in the sense of Definition~ \ref{def:c19-lrc}) with \)d ≥n - k - k/r+ 2\(. By the Singleton-type bound of Theorem~ \ref{thm:c19-singleton-lrc} (applied to the mLRC obtained by restricting to any \)k\( coordinates on which \)C^*\( projects bijectively), this distance cannot exceed \)n - k - k/r+ 2\(, so equality holds and \)C^*\( meets the bound exactly. \)