Locally recoverable code: Difference between revisions

Revision as of 21:28, 16 November 2024

Latest revision as of 05:28, 6 January 2025

(19 intermediate revisions by 6 users not shown)

Line 1:

{{Short description|Coding Theory}}

{{Orphan|date=November 2024}}

'''Locally recoverable codes''' are a family of [[error correction code]]s that were introduced first by D. S. Papailiopoulos and A. G. Dimakis<ref>{{Citation

|first1=Dimitris S.|last1=Papailiopoulos |first2=Alexandros G. |last2=Dimakis |contribution=Locally repairable codes |pages=2771–2775 |___location=Cambridge, MA, USA |title=2012 IEEE International Symposium on Information Theory Proceedings |date=2012 |doi=10.1109/ISIT.2012.6284027|isbn=978-1-4673-2579-0 |arxiv=1206.3804 |publisher=IEEE}}</ref> and have been widely studied in [[information theory]] due to their applications related to distributive and [[cloud storage]] systems.<ref>{{Citation

|first1=A.

|last1=Barg

Line 18 ⟶ 17:

|arxiv=1603.08876

|isbn=978-1-4673-7704-1

|publisher=IEEE

}}</ref><ref>{{Citation

|first1=V. R.

Line 30:

|issue=11

|doi=10.1109/TIT.2015.2477406

|publisher=IEEE

}}</ref><ref>{{Citation

|first1=A.

Line 44 ⟶ 45:

|issue=6

|doi= 10.1007/s10623-022-01046-y

|publisher=IEEE

|arxiv=2104.01434

}}</ref><ref>{{Citation

|first1=K.

Line 58 ⟶ 61:

An <math>[n, k, d, r]_{q}</math> LRC is an <math>[n, k, d]_{q}</math> [[linear code]] such that there is a [[Function (mathematics)|function]] <math>f_{i}</math> that takes as input <math>i</math> and a [[Set (mathematics)|set]] of <math>r</math> other [[Coordinate system|coordinates]] of a codeword <math>c = (c_{1}, \ldots, c_{n}) \in C</math> different from <math>c_{i}</math>, and outputs <math>c_{i}</math>.

==Overview==

[[Error correction code|Erasure-correcting codes]], or simply [[Error correction code|erasure codes]], for distributed and [[cloud storage]] systems, are becoming more and more popular as a result of the present spike in demand for [[cloud computing]] and storage services. This has inspired researchers in the fields of [[Information theory|information]] and [[coding theory]] to investigate new facets of codes that are specifically suited for use with storage systems.

It is well-known that LRC is a [[linear code|code]] that needs only a limited [[Set (mathematics)|set]] of other symbols to be accessed in order to restore every symbol in a codeword. This idea is very important for distributed and [[cloud storage]] systems since the most common error case is when one storage node fails (erasure). The main objective is to recover as much [[data]] as possible from the fewest additional storage nodes in order to restore the node. Hence, Locally Recoverable Codes are crucial for such systems.

The following [[definition]] of the LRC follows from the description above: an <math>[n, k, r]</math>-Locally Recoverable Code (LRC) of length <math>n</math> is a [[linear code|code]] that produces an <math>n</math>-symbol codeword from <math>k</math> information symbols, and for any symbol of the codeword, there exist at most <math>r</math> other symbols such that the value of the symbol can be recovered from them. The locality [[parameter]] satisfies <math>1 \leq r \leq k</math> because the entire codeword can be found by accessing <math>k</math> symbols other than the erased symbol. Furthermore, Locally Recoverable Codes, having the minimum [[Hamming distance|distance]] <math>d</math>, can recover <math>d-1</math> erasures.

==Definition==

Let <math>C</math> be a <math>[n, k, d]_{q}</math> [[linear code]]. For <math>i \in \{1, \ldots, n\}</math>, let us denote by <math>r_{i}</math> the minimum number of other [[Coordinate system|coordinates]] we have to look at to recover an erasure in [[Coordinate system|coordinate]] <math>i</math>. The number <math>r_{i}r_i</math> is said to be the ''locality of the <math>i</math>-th [[Coordinate system|coordinate]]'' of the code. The ''locality'' of the code is defined as <div style="text-align: center;"><math>r = \textrm{max}\{r_{i}|r_i \mid i \in \{1, \ldots, n\}\}.</math></div>

An <math>[n, k, d, r]_{q}</math> ''locally recoverable code'' (LRC) is an <math>[n, k, d]_{q}_q</math> [[linear code]] <math>C \in \mathbb F_q^n</math> with locality <math>r</math>.

Let <math>C</math> be an <math>[n, k, d]_{q}_q</math>-locally recoverable code. Then an erased component can be recovered linearly,<ref>{{Citation

|first1=Dimitris S.|last1=Papailiopoulos |first2=Alexandros G. |last2=Dimakis |contribution=Locally repairable codes |pages=2771–2775 |___location=Cambridge, MA, USA |publishertitle=2012 IEEE International Symposium on Information Theory |date=2012 |doi=10.1109/ISIT.2012.6284027|isbn=978-1-4673-2579-0 |arxiv=1206.3804 }}</ref> i.e. for every <math>i \in \{1, \ldots, n\}</math>, the space of [[linear equation]]s of the code contains [[Element (mathematics)|elements]] of the form <math> x_{i}x_i = f(x_{i_{1}i_1}, \ldots, x_{i_{r}i_r})</math>, where <math>i_{j}i_j \neq i</math>.

==Optimal locally recoverable codes==

'''Theorem'''<ref>{{Citation

|first1=V. |last1=Cadambe |first2=A. |last2=Mazumdar |contribution=An upper bound on the size of locally recoverable codes |pages=1–5 |___location=Calgary, AB, Canada |title=2013 International Symposium on Network Coding |date=2013 |doi=10.1109/NetCod.2013.6570829|arxiv=1308.3200 |isbn=978-1-4799-0823-3 }}</ref> Let <math>n = (r+1)s</math> and let <math>C</math> be an <math>[n, k, d]_{q}</math>-locally recoverable code having <math>s</math> disjoint locality [[Disjoint sets|sets]] of size <math>r+1</math>. Then <div style="text-align: center;"><math>d \leq n - k - \left\lceil\frac{k}{r}\right\rceil + 2.</math></div>

An <math>[n, k, d, r]_{q}</math>-LRC <math>C</math> is said to be optimal if the minimum [[Hamming distance|distance]] of <math>C</math> satisfies <div style="text-align: center;"><math>d = n - k - \left\lceil\frac{k}{r}\right\rceil + 2 .</math></div>

== Tamo–Barg codes ==

Line 99 ⟶ 110:

:• Suppose that a <math>(r, \ell)</math>-good polynomial <math>f(x)</math> over <math>\mathbb F_{q}</math> is given with splitting covering <math>i \in \{1, \ldots, \ell\}</math>.

:• Let <math>s \leq \ell-1</math> be a positive [[integer]].

:• Consider the following <math>\mathbb F_{q}F_q</math>-[[vector space]] of [[polynomial]]s <math display="block">V = \left\{\sum_{i=0}^s g_{i}g_i(x)f(x)^i: \deg(g_{i}g_i(x)) \leq \deg(f(x))-2 \right\}.</math>

:• Let <math display="inline">T = \bigcup_{i=1}^\ell A_i</math>.

:• The code <math> \{ ev_\operatorname{Tev}_T(g):g \in V \}</math> is an <math>((r+1)\ell,(s+1)r,d,r)</math>-optimal locally coverable code, where <math>ev_\operatorname{Tev}_T</math> denotes evaluation of <math>g</math> at all points in the [[Set (mathematics)|set]] <math>T</math>.

=== Parameters of Tamo–Barg codes ===

Line 123 ⟶ 134:

Thus, we can use the obtained encoding [[polynomial]] if we take our [[data]] to encode as the [[Row and column vectors|row vector]] <math>a = </math> <math>(a_{0,0}, a_{0,1}, a_{1,0}, a_{1,1}, a_{2,0}, a_{2,1}, a_{3,0}, a_{3,1})</math>. Encoding the [[Vector (mathematics and physics)|vector]] <math>m</math> to a length 15 message [[Vector (mathematics and physics)|vector]] <math>c</math> by multiplying <math>m</math> by the [[generator matrix]]

: <div style="text-align: center;"><math>

<math>

G = \begin{pmatrix}

1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\

Line 134 ⟶ 145:

1 & 16 & 37 & 10 & 18 & 10 & 37 & 1 & 16 & 18 & 1 & 37 & 10 & 18 & 16

\end{pmatrix}

. </math></div>

For example, the encoding of information [[Vector (mathematics and physics)|vector]] <math>m = (1, 1, 1, 1, 1, 1, 1, 1)</math> gives the codeword <math>c = mG = (8, 8, 5, 9, 21, 3, 36, 31, 32, 12, 2, 20, 37, 33, 21)</math>.

Line 142 ⟶ 153:

==Locally recoverable codes with availability==

A code <math>C</math> has all-symbol locality <math>r</math> and availability <math>t</math> if every code symbol can be recovered from <math>t</math> disjoint repair sets of other symbols, each [[Set (mathematics)|set]] of [[Cardinality|size]] at most <math>r</math> symbols. Such codes are called <math>(r,t)_a</math>-LRC.<ref>{{Citation

'''Definition'''<ref>{{Citation

|first1=P. |last1=Huang |first2=E. |last2=Yaakobi |first3=H.|last3=Uchikawa |first4=P.H.|last4=Siegel |title="Linear locally repairable codes with availability" |chaptercontribution=Linear locally repairable codes with availability |pages=1871–1875 |___location=Hong Kong, China |publishertitle=2015 IEEE International Symposium on Information Theory |date=2015 |doi=10.1109/ISIT.2015.7282780|isbn=978-1-4673-7704-1 }}</ref> A code <math>C</math> has all-symbol locality <math>r</math> and availability <math>t</math> if every code symbol can be recovered from <math>t</math> disjoint repair [[Disjoint sets|sets]] of other symbols, each [[Set (mathematics)|set]] of [[Cardinality|size]] at most <math>r</math> symbols. Such codes are called <math>(r,t)_a</math>-LRC.

'''Theorem'''<ref>{{Citation |first1=I. |last1=Tamo |first2=A. |last2=Barg |title="Bounds on locally recoverable codes with multiple recovering sets" |chapter=Bounds on locally recoverable codes with multiple recovering sets |pages=691–695 |___location=Honolulu, HI, USA |publisher=2014 IEEE International Symposium on Information Theory |date=2014 |doi=10.1109/ISIT.2014.6874921|arxiv=1402.0916 |isbn=978-1-4799-5186-4 }}</ref> The minimum [[Hamming distance|distance]] of <math>[n,k,d]_q</math>-LRC having locality <math>r</math> and availability <math>t</math> satisfies the [[Upper and lower bounds|upper bound]]

<div style="text-align: center;"><math>d \leq n - \sum_{i=0}^{t} \left\lfloor\frac{k-1}{r^i}\right\rfloor.</math></div>.

If the code is [[Systematic code|systematic]] and locality and availability apply only to its information symbols, then the code has information locality <math>r</math> and availability <math>t</math>, and is called <math>(r,t)_i</math>-LRC.<ref>{{Citation |first1=I. |last1=Tamo |first2=A. |last2=Barg |contribution=Bounds on locally recoverable codes with multiple recovering sets |pages=691–695 |___location=Honolulu, HI, USA |title=2014 IEEE International Symposium on Information Theory |date=2014 |doi=10.1109/ISIT.2014.6874921|arxiv=1402.0916 |isbn=978-1-4799-5186-4 }}</ref>

<div style="text-align: center;"><math>d \leq n - \sum_{i=0}^{t} \left\lfloor\frac{k-1}{r^i}\right\rfloor</math></div>.

If the code is [[Systematic code|systematic]] and locality and availability apply only to its information symbols, then the code has information locality <math>r</math> and availability <math>t</math>, and is called <math>(r,t)_i</math>-LRC.

'''Theorem'''<ref>{{Citation

|first1=A. |last1=Wang |first2=Z. |last2=Zhang |title="Repair locality with multiple erasure tolerance" |pages=6979–6987 |journal=IEEE Transactions on Information Theory |date=2014 |volume=60 |issue=11 |doi=10.1109/TIT.2014.2351404|arxiv=1306.4774 }}</ref> The minimum [[Hamming distance|distance]] <math>d</math> of an <math>[n,k,d]_q</math> linear <math>(r,t)_i</math>-LRC satisfies the [[Upper and lower bounds|upper bound]]

<div style="text-align: center;"><math>d \leq n-k-\left\lceil\frac{t(k-1)+1}{t(r-1)+1}\right\rceil+2.</math></div>.

<div style="text-align: center;"><math>d \leq n-k-\left\lceil\frac{t(k-1)+1}{t(r-1)+1}\right\rceil+2</math></div>.

== References ==

Line 160 ⟶ 168:

{{reflist}}

[[Category:Cryptography]]

[[Category:Information theory]]

[[Category:Mathematics]] [[Category:Cryptography]] [[Category:Information theory]] [[Category:Error detection and correction]]