Content deleted Content added
Valentine789 (talk | contribs) m Added links to other pages |
m Open access bot: arxiv updated in citation with #oabot. |
||
| (35 intermediate revisions by 9 users not shown) | |||
Line 1:
{{Short description|Coding Theory}}
'''Locally
|first1=Dimitris S.|last1=Papailiopoulos |first2=Alexandros G. |last2=Dimakis |
▲'''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 |title="Locally Repairable Codes" |chapter=Locally repairable codes |pages=2771–2775 |___location=Cambridge, MA, USA |publisher=IEEE International Symposium on Information Theory |date=2012 |doi=10.1109/ISIT.2012.6284027|isbn=978-1-4673-2579-0 }}</ref> and have been widely studied in [[Information theory]] due to their applications related to Distributive and [[Cloud storage|Cloud Storage]] Systems.<ref>{{Citation
|first1=A.
|last1=Barg
Line 10 ⟶ 9:
|first3=S.
|last3=Vlăduţ
|
|pages=1252–1256
|___location=Hong Kong, China
|
|date=2015
|doi=10.1109/ISIT.2015.7282656
|arxiv=1603.08876
|isbn=978-1-4673-7704-1
|publisher=IEEE
}}</ref><ref>{{Citation
|first1=V. R.
Line 24 ⟶ 23:
|first2=A.
|last2=Mazumdar
|title=
|pages=5787–5794
|journal=IEEE Transactions on Information Theory
Line 31 ⟶ 30:
|issue=11
|doi=10.1109/TIT.2015.2477406
|publisher=IEEE
}}</ref><ref>{{Citation
|first1=A.
Line 38:
|first3=G.
|last3=Micheli
|title=
|journal=Designs, Codes and Cryptography
|pages=1427–1436
Line 45:
|issue=6
|doi= 10.1007/s10623-022-01046-y
|publisher=IEEE
|arxiv=2104.01434
}}</ref><ref>{{Citation
|first1=K.
Line 52 ⟶ 54:
|first3=G.
|last3=Matthews
|title=
|date=2022
|doi=10.3934/amc.2018020
|doi-access=free
}}</ref>
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>
An <math>[n, k, d, r]_{q}</math> ''locally recoverable code'' (LRC) is an <math>[n, k, d]
Let <math>C</math> be an <math>[n, k, d]
|first1=Dimitris S.|last1=Papailiopoulos |first2=Alexandros G. |last2=Dimakis |
==Optimal
'''Theorem'''<ref>{{Citation
|first1=V. |last1=Cadambe |first2=A. |last2=Mazumdar |
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>
==
Let <math>f
:• <math>f</math> has [[Degree of a polynomial|degree]] <math>r+1</math>,
:• there exist distinct [[subset]]s <math>A_{1}
::– for any <math>i \in \{1, \ldots, \ell\}</math>, <math>f
::–
::– <math>A_{i}
We say that {<math>A_{1},\ldots,A_{\ell}</math>} is a splitting covering for <math>f</math>.<ref>{{Citation |first1=G.
|last1=Micheli |title=
|arxiv=1806.11492 }}</ref>
===
The
|first1=I.|last1=Tamo |first2=A. |last2=Barg |
:• 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
:• Consider the following <math>\mathbb
<div style="text-align: center;"><math>V = \{\sum_{i=0}^s g_{i}(x)f(x)^i:{\text{deg}}(g_{i}(x)) \leq {\text{deg}}(f(x))-2\}</math></div>▼
:• The code <math> \{
▲:• Let <math>T</math> = <math display="inline">\bigcup_{i=1}^\ell A_i</math>
▲:• The code <math> \{ ev_{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_{T}</math> denotes evaluation of g at all points in the set <math>T</math>.
=== Parameters of
:• '''Length.''' The length is the number of evaluation points. Because the [[Set (mathematics)|sets]] <math>A_i</math> are [[Disjoint sets|disjoint]] for <math>i \in \{1, \ldots, \ell\}</math>, the length of the code is <math>|T| = (r+1)\ell</math>.
:• '''Dimension.''' The [[dimension]] of the code is <math>(s+1)r</math>, for <math>s</math> ≤ <math>\ell-1</math>, as each <math>g_i</math> has [[Degree of a polynomial|degree]] at most <math>
:• '''Distance.''' The [[Hamming distance|distance]] is given by the fact that <math>V \subseteq \mathbb F_q [x]_{\leq k}</math>, where <math>k = r + 1 - 2 + s(r+1)</math>, and the obtained code is the [[Reed–Solomon error correction|Reed-Solomon code]] of [[Degree of a polynomial|degree]] at most <math>k</math>, so the minimum [[Hamming distance|distance]] equals <math>(r+1)\ell-((r+1)-2+s(r+1))</math>.
:• '''Locality.''' After the erasure of the single component, the evaluation at <math>a_i \in A_i</math>, where <math>|A_i|=r+1</math>, is unknown, but the evaluations for all other <math>a \in A_i</math> are known, so at most <math>r</math> evaluations are needed to uniquely determine the erased component, which gives us the locality of <math>r</math>.
: To see this, <math>g</math> restricted to <math>A_j</math> can be described by a [[polynomial]] <math>h</math> of [[Degree of a polynomial|degree]] at most <math>
=== Example of
We will use <math>x^5 \in \mathbb F_{41} [x]</math> to construct <math>[15, 8, 6, 4]</math>-LRC. Notice that the [[Degree of a polynomial|degree]] of this [[polynomial]] is 5, and it is [[Constant (mathematics)|constant]] on <math>A_i</math> for <math>i \in \{1, \ldots, 8\}</math>, where <math>A_1 = \{1, 10, 16, 18, 37\}</math>, <math>A_2 = 2A_1</math>, <math>A_3 = 3A_1</math>, <math>A_4 = 4A_1</math>, <math>A_5 = 5A_1</math>, <math>A_6 = 6A_1</math>, <math>A_7 = 11A_1</math>, and <math>A_8 = 15A_1</math>: <math>A_1^5 = \{1\}</math>, <math>A_2^5 = \{32\}</math>, <math>A_3^5 = \{38\}</math>, <math>A_4^5 = \{40\}</math>, <math>A_5^5 = \{9\}</math>, <math>A_6^5 = \{27\}</math>, <math>A_7^5 = \{3\}</math>, <math>A_8^5 = \{14\}</math>. Hence, <math>x^5</math> is a <math>(4,8)</math>-good polynomial over <math>\mathbb F_{41}</math> by the definition. Now, we will use this [[polynomial]] to construct a code of [[dimension]] <math>k = 8</math> and length <math>n = 15</math> over <math>\mathbb F_{41}</math>. The locality of this code is 4, which will allow us to recover a single [[Server (computing)|server]] failure by looking at the information contained in at most 4 other [[Server (computing)|servers]].
Next, let us define the encoding [[polynomial]]: <math>f_a(x) = \sum_{i=0}^{r - 1} f_i(x)x^i</math>, where <math>f_i(x) = \sum_{i=0}^{\frac{k}{r} - 1} a_{i,j}g(x)^j</math>. So, <math>f_a(x) =</math> <math>a_{0,0} +</math> <math>a_{0,1}x^5 +</math> <math>a_{1,0}x +</math> <math>a_{1,1}x^6 +</math> <math>a_{2,0}x^2 +</math> <math>a_{2,1}x^7 +</math> <math>a_{3,0}x^3 +</math> <math>a_{3,1}x^8</math>.
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>
G = \begin{pmatrix}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\
Line 135 ⟶ 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>.
Observe that we constructed an optimal LRC; therefore, using the [[Singleton bound]], we have that the [[Hamming distance|distance]] of this code is <math>d = n - k - \left\lceil\frac{k}{r}\right\rceil + 2 = 15 - 8 - 2 + 2 = 7</math>. Thus, we can recover any 6 erasures from our codeword by looking at no more than 8 other components.
==Locally
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
|first1=P. |last1=Huang |first2=E. |last2=Yaakobi |first3=H.|last3=Uchikawa |first4=P.H.|last4=Siegel |
'''Theorem'''
▲<div style="text-align: center;"><math>
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>.▼
'''Theorem'''<ref>{{Citation
|first1=A. |last1=Wang |first2=Z. |last2=Zhang |title=
▲<div style="text-align: center;"><math>d \leq n
== References ==
Line 161 ⟶ 168:
{{reflist}}
[[Category:Cryptography]]
[[Category:Information theory]]
[[Category:Error detection and correction]]
| |||