Computer Science 5th Year Master's Thesis Presentation

— 11:30am

Location:
In Person - Traffic21 Classroom, Gates Hillman 6501

Speaker:
SARANSH CHOPRA, Masters Student, Computer Science Department, Carnegie Mellon University
https://saranshchopra.github.io/

Low Field Size Constructions of Access-Optimal Convertible Codes

Most large-scale storage systems employ erasure coding to provide resilience against disk failures. Recent work has shown that tuning this redundancy to changes in disk failure rates leads to substantial storage savings. This process requires code conversion, wherein data encoded using an [nI,kI] initial code has to be transformed into data encoded using an [nF,kF] final code.  Convertible codes are a class of codes that enable efficient code conversion while maintaining other desirable properties. In this thesis, we focus on the access cost of conversion (corresponding to the total number of symbols accessed in the conversion process) and on an important subclass of conversions known as the merge regime (corresponding to combining multiple initial codewords into a single final codeword).

In this setting, explicit constructions are known for systematic access-optimal Maximum Distance Separable (MDS) convertible codes for all parameters in the merge regime. However, the existing construction for a key subset of these parameters, which makes use of Vandermonde parity matrices, requires a very large field making it unsuitable for practical applications. In this thesis, we provide (1) sharper bounds on the minimum field size requirement for such codes, and (2) explicit constructions for low field sizes for several parameter ranges. In doing so, we provide a proof of super-regularity of specially designed classes of Vandermonde matrices that could be of independent interest. 

Thesis Committee 

Rashmi Vinayak (Chair)
Ryan O'Donnell

Additional Information