SILO: Rashi Vinayak – FESCH.TV

FESCH.TV INFORMIERT:

Date: 2021-05-12

Title: Convertible Codes: Efficient Conversion of Coded Data in Large-scale Storage Systems

Abstract: In large-scale data storage systems, failures are the norm in day-to-day operations. To protect data in the face of such failures, erasure codes (a tool from coding theory) are employed to store data in a redundant fashion.  In this setting, a set of k data blocks to be stored is encoded using an [n, k] code to generate n blocks that are then stored on distinct storage devices. In a recent work, we showed that the failure rate of storage devices vary considerably over time, and that dynamically tuning the parameters n and k of the code provides significant reduction in storage cost. However, traditional codes suffer from prohibitively high resource overheads in changing the code parameters on already encoded data.

Motivated by this application, in this talk, we:
1. Present a new theoretical framework to formalize the notion of „code conversion“—the process of converting data encoded using an [n, k] code into data encoded using a code with different parameters [n‘, k‘], while maintaining desired decodability properties,
2. Introduce „convertible codes“, a new class of codes that enable resource-efficient conversion,
3. Prove tight bounds on two important metrics for code conversion (a) the number of nodes accessed, and (b) bandwidth consumed,
4. Present practical constructions of convertible codes for a broad range of parameters.