Tuesday, June 11 2019
11:30 - 13:00

Alladi Ramakrishnan Hall

Sub-packetization of Minimum Storage Regenerating Codes: A lower bound and a work-around

Venkat Guruswami

Carnegie Mellon University

Modern cloud storage systems need to store vast amounts of data in a fault tolerant manner, while also preserving data reliability and accessibility in the wake of frequent server failures. Traditional MDS (Maximum Distance Separable) codes provide the optimal trade-off between redundancy and number of worst-case erasures tolerated. Minimum storage regenerating (MSR) codes are a special sub-class of MDS codes that provide mechanisms for exact regeneration of a single code-block by downloading the minimum amount of information from the remaining code-blocks. As a result, MSR codes are attractive for use in distributed storage systems to ensure node repairs with optimal repair-bandwidth. However, all known constructions of MSR codes require large sub-packetization levels (which is a measure of the granularity to which a single vector codeword symbol needs to be divided into for efficient repair). This restricts the applicability of MSR codes in practice.

This talk will present a lower bound that exponentially large sub-packetization is inherent for MSR codes. We will also propose a natural relaxation of MSR codes that allows one to circumvent this lower bound, and present a general approach to construct MDS codes that significantly reduces the required sub-packetization level by incurring slightly higher repair-bandwidth as compared to MSR codes.

The lower bound is joint work with Omar Alrabiah, and the constructions are joint work with Ankit Rawat, Itzhak Tamo, and Klim Efremenko.

Download as iCalendar