LOW FIELD SIZE CONSTRUCTIONS OF ACCESS OPTIMAL CONVERTIBLE CODES

Abstract

Large-scale storage systems typically use erasure coding to ensure data durability against disk failures. Recent research indicates that adjusting the level of redundancy based on varying disk failure rates can lead to significant storage efficiency improvements. This adjustment involves code conversion, where data originally encoded with a code needs to be re-encoded into a code, a process that can be resource- demanding. Convertible codes offer a way to facilitate this transformation efficiently while preserving other valuable properties. This project examines the access cost of conversion, defined as the total number of code symbols accessed during the process, and explores a specific type of conversion called the merge regime, which consolidates multiple initial codewords into one final codeword. Although systematic, access-optimal Maximum Distance Separable (MDS) convertible codes for all parameters in the merge regime have been established, the current method for a key subset of these parameters relies on Left Shift parity matrices, requiring a large field size and thus limiting its practical usability. In this work, we present (1) improved bounds on the minimum field size needed for such codes and (2) probabilistic constructions that support lower field sizes for a variety of parameter ranges, utilizing the Combinatorial Nullstellensatz theorem.