The Exact Repair Problem: Using Reed-Solomon Codes
Translated title
The Exact Repair Problem
Author
Jensen, Jonas Junker
Term
4. term
Education
Publication year
2019
Submitted on
2019-06-06
Pages
55
Abstract
Mængden af digitale data vokser, hvilket lægger et stigende pres på lagerservere. En udbredt løsning er at opdele hver fil på mange servere i et distribueret lagersystem, så data kan overleve, hvis en enkelt server fejler. Redundans tilføjes med fejlkorrigerende koder, som gør det muligt at genskabe mistede dele. Mange afkodningsmetoder rekonstruerer dog hele den kodede fil (codeword) i stedet for kun den manglende del. Det fører til exact repair‑problemet (ERP): hvordan man præcist genskaber dataene på en fejlet server uden at genopbygge det hele. Denne afhandling undersøger ERP for Reed–Solomon (RS)‑koder over udvidelseslegemer (algebraiske udvidelser af endelige legemer). Når en fil er fordelt som et RS‑codeword, kan en løsning på ERP præcist genskabe indholdet på en hvilken som helst fejlet server. Afhandlingen fokuserer på lineære exact repair‑skemaer, hvor reparationen bruger lineære kombinationer af data fra de resterende servere. Tilgangen kombinerer Galois‑teori, kodningsteori og lineær algebra med det formål at designe et optimalt reparationsskema i denne sammenhæng.
Digital data volumes keep growing, which puts increasing pressure on storage servers. A common response is to split each file across many servers in a distributed storage system so the data can survive a single server failure. Redundancy is added with error-correcting codes, which allow lost pieces to be recovered. However, many decoding methods reconstruct the entire encoded file (the codeword) rather than just the missing part. This leads to the exact repair problem (ERP): how to restore exactly the data stored on a failed server without rebuilding everything. This thesis studies ERP for Reed–Solomon (RS) codes over extension fields (algebraic extensions of finite fields). When a file is distributed as an RS codeword, a solution to ERP can reconstruct the contents of any failed server precisely. The thesis focuses on linear exact repair schemes, where the repair uses linear combinations of data from the remaining servers. The approach combines Galois theory, coding theory, and linear algebra, with the aim of designing an optimal repair scheme in this setting.
[This abstract was generated with the help of AI]
Documents