On error correcting codes for distributed storage

Two popular directions of error correcting codes for distributed storage are codes with additional recovery or regenerating properties. First we have codes for additional recovery properties. Codewords in array format find applications in disk storage where columns are stored on different disks in combination with parity checks across disks that protect data against disk failures. The addition of global parities protects against sector failures on any of the disks while keeping storage overhead low. We construct sector-disk array codes that tolerate any combination of two disk failures and three sector failures with minimal overhead. This constructs for the first time codes with these parameters without relying on exhaustive search. In the regenerating direction we have some modified layered codes in a two stage construction that gives regenerating codes with small field size. For more general parameters we define a Johnson graph code as a subspace of labelings of the vertices in a Johnson graph with the property that labelings are uniquely determined by their restriction to vertex neighborhoods specified by the parameters of the code. We give a construction and main properties for the codes. We show their role in the concatenation of layered codes to give regenerating codes for storage systems. Focusing on the Minimum Storage regenerating (MSR) point with $d=n-1$, we present graphical representations of codes with parameters \\ ((n,k,d), (α, β)) = ((qt, q(t-1), qt-1),(q^t, q^t-1)) over small field size.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Mathematics

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2020

Author dc:creator

• Li, Xiao

Contributors dc:contributor

• Duursma, Iwan
• Reznick, Bruce
• Yong, Alexander
• Milenkovic, Olgica

• Coding Theory, Distributed Storage

Statement dc:rights

• Copyright 2020 Xiao Li

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/107954

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/107954