Locally recoverable code: Difference between revisions

Revision as of 15:30, 21 September 2024

Revision as of 15:36, 21 September 2024

Line 84:

::– <math>A_{i}</math> ∩ <math>A_{j}</math> = ∅ for any <math>i</math> ≠ <math>j</math>.

We say that {<math>A_{1},\ldots,A_{\ell}</math>} is a splitting covering for <math>f</math><ref>{{Citation |first1=G.

|first1=I.|last1=Tamo |first2=A. |last2=BargMicheli |title="A familyConstructions of optimalLocally locallyRecoverable recoverableCodes codeWhich are Optimal" |pages=686167-690 |___location=Honolulu, HI, USA175 |publisher=IEEE International SymposiumTransactions on Information Theory |date=20142020 |doi=10.1109/ISITTIT.20142019.6874920}}</ref>. 2939464

}}</ref>.

=== Tamo--Barg Construction ===

The Tamo--Barg construction utilizes good polynomials.<ref>{{Citation

|first1=I.|last1=Tamo |first2=A. |last2=Barg |title="A family of optimal locally recoverable code" |pages=686-690 |___location=Honolulu, HI, USA |publisher=IEEE International Symposium on Information Theory |date=2014 |doi=10.1109/ISIT.2014.6874920}}</ref>

|first1=G.

|last1=Micheli

|title="Constructions of Locally Recoverable Codes Which are Optimal"

|pages=167-175

|publisher=IEEE Transactions on Information Theory

|date=2020

|doi=10.1109/TIT.2019.2939464

}}</ref>

:• 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</math> ≤ <math>\ell-1</math> be a positive integer.

Line 119 ⟶ 113:

=== Example of Tamo-Barg Construction ===

To design such a system, weWe 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 this polynomial is 5, and it is 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 failure by looking at the infromation contained in at most 4 other servers.

Suppose that we want to design a distributive storage system using 15 servers that allows to recover the data of a single server failure by looking at the infromation contained in at most 4 other servers and allows to recover the data contained in any 7 servers (when they simultaneously fail) by looking at the infromation contained in at most 8 other servers.

To design such a system, we will use <math>x^5 \in \mathbb F_{41} [x]</math>. Notice that the degree of this polynomial is 5, and it is 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 failure by looking at the infromation contained in at most 4 other servers.

Next, let's 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>.

Line 142 ⟶ 134:

For example, the encoding of information 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 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 will be able to recover the data contained in any 7 servers (when they simultaneously fail) by looking at the information contained in at most 8 other servers.

Therefore, we have designed a desired distributive storage system.

==Locally Recoverable Codes with Availability==