High-rate MSR Codes, Interior-point Regenerating Codes, and Codes with Hierarchical Locality
P S Birenjith · 2019
Given the breath-taking pace at which the amount of data being generated on a daily basis is growing, and the keen desire to extract information from this data, there is strong interest within the storage industry, at finding means to efficiently and reliably store this data. Given that individual storage units are prone to failure, data pertaining to a single _le is distributed across storage nodes. Such storage of `Big Data' across a spatially distributed network of nodes, calls for codes than can efficiently handle the issue of node repair. The need for node repair could arise on account of device failure, need for a maintenance reboot, or simply because the node is busy serving other demands. A new branch of coding theory has sprung up in response. Regenerating codes minimize data download during a repair operation, while codes with locality ensure that local operations suffice for node repair. The present thesis makes contributions to both regenerating codes as well as codes with locality. While the reliable storage of data in disks with minimum storage overhead is a well-studied problem, the problem of node repair is relatively new. From the viewpoint of the storage industry, the cost to repair a failed node can be measured in two distinct ways: firstly, in terms of the number of surviving nodes accessed, and secondly, in terms of the amount of data transmitted over the network to ensure repair of the failed node. In a regenerating code having parameter set (n; k; d; (_; _);B), and over a _finite _field Fq, a file consisting of B symbols from Fq is encoded into n_ symbols, and the coded symbols are stored in n distinct nodes, each node storing _ symbols. The parameter _ is referred to as sub-packetization level. The entire _le can be recovered from downloading k_ symbols from any set of k nodes. Under the exact-repair (ER) setting that is of interest here, the contents of a failed node are repaired exactly from a total of d_ symbols downloaded from any d helper nodes, each helper node transmitting _ symbols. In the alternative setting of functional repair (FR), the contents of the replacement node can be different from that of the failed node, however, following node repair, the new configuration is still required to satisfy the data-recovery and node repair properties of a regenerating code. Under the FR setting, there is a trade-off known as storage-repair-bandwidth (S-RB) trade-off between the values of _ and d_, that optimize the size of the _le being stored. The two extreme points of the trade-off, one corresponding to the minimum possible value of _ and the other, to the minimum possible value of d_, are known as the minimum-storage-regenerating (MSR) and minimum-bandwidth-regenerating (MBR) points respectively. It has been shown that the extreme points of the ER trade-off coincide with those of the FR trade-off. However, the characterization of trade-off in the case of ER remains an open and challenging problem. High-rate MSR code constructions the _first problem reported…