ROBUSTNESS AND FLEXIBILITY IN CODING FOR DISTRIBUTED STORAGE SYSTEMS

This dissertation presents new methods for analysis and design of coding schemes for distributed storage. We introduce a generalization of the regenerating codes by simultaneously incorporating flexibility and error resiliency in the code design. For flexibility we consider bandwidth-adaptive repair, which allows selecting the number of helpers during the runtime, while achieving optimal repair bandwidth adaptively. We also consider robustness against an omniscient adversary, which can control a limited number of nodes, to ensure a desired level of error resiliency. In this extended setting, we formulate the optimum trade-off between the storage overhead and repair bandwidth. After deriving the theoretical lower bounds on storage overhead and repair bandwidth, we focus our attention to explicit code construction for the extreme points of this trade-off, achieving theminimumrepair bandwidth (theMBR code) and the minimum storage overhead (the MSR code). For each case we present novel explicit codes and show that these codes achieve the optimal trade-off for bandwidth-adaptive and error-resilient (BAER) setting. All of the code constructions in this dissertation are designed in a well-known framework called Product Matrix, which is widely accepted to be practically appealing for implementation. An important feature of all these codes is their exact repair mechanism that guarantees recovering the same content of any failed storage node. In the MBR BAER case we present two coding schemes. The first one requires the code alphabet size to be large, but adds no restrictions to the choice of other code parameters compared to non-BAER codes. In the second MBR BAER code, alphabet size can be bounded by the number of nodes in the system, which is similar to practical solutions such as the Reed-Solomon codes, at the cost of some extra restrictions on the subpacketization level. To the best of our knowledge these are the first exact-repair BAER MBR codes. We also present an explicit MSR BAER code construction, and show that it can perform optimal exact repair for a wide range of choices for the number of helpers, while realizing an exponentially smaller subpacketization level compared to the only other existing solution.Ph.D