Distributed storage systems from combinatorial designs

Large scale distributed storage systems are used in several contexts, such as social networking sites (Facebook, Google+ etc.) and cloud storage (Amazon, Microsoft etc.). The widespread adoption of these systems has introduced several new research problems. For instance, these systems often consist of individually unreliable nodes; however, the overall system needs to have reliable data access. When nodes fail, the system needs to be repaired in a speedy manner, by consuming as few resources (drives accessed, energy etc.) as possible. In recent years, there has been a lot of interest in the design of regenerating codes which are erasure codes targeted towards distributed storage systems.
In this talk, I will discuss our recent work on constructing regenerating codes from combinatorial designs. Combinatorial design theory has its roots in recreational mathematics and is concerned with the arrangement of the elements of a finite set into subsets, such that the collection of subsets has certain “nice” properties. I will discuss our code constructions that are derived from Steiner systems, affine geometries, Hadamard designs, mutually orthogonal Latin squares and high-girth graphs. Our codes allow for failure recovery by simply downloading packets from the surviving nodes and allow for the repair degree (i.e., the number of nodes contacted for node repair) to be varied in a simple manner. We also construct local codes, where the repair degree is smaller than the number of nodes contacted for reconstructing the stored file. Determining the code rate of these constructions is challenging and prior work has primarily provided lower bounds on the rate. For most of our constructions we are able to determine the code rate for a range of code parameters.