On error correcting codes for distributed storage

Li, Xiao

Permalink

https://hdl.handle.net/2142/107954 Copy

Description

Title

On error correcting codes for distributed storage

Author(s)

Li, Xiao

Issue Date

2020-05-05

Director of Research (if dissertation) or Advisor (if thesis)

Duursma, Iwan

Doctoral Committee Chair(s)

Reznick, Bruce

Committee Member(s)

• Yong, Alexander
• Milenkovic, Olgica

Department of Study

Mathematics

Discipline

Mathematics

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

Coding Theory, Distributed Storage

Abstract

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), (\alpha, \beta)) = ((qt, q(t-1), qt-1),(q^t, q^{t-1}))$ over small field size.

Graduation Semester

2020-05

Type of Resource

Thesis

Permalink

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

Copyright and License Information

Copyright 2020 Xiao Li

Owning Collections