On Matroid Theory and Distributed Data Storage

Abstract

The fast development of web services and cloud computing has generated an enormous amount of digital data. Huge data centers were therefore built to store and remotely access this data. A distributed storage system consists of a network of storage servers where the data is distributed among these servers. The main challenge in the design of such systems is to guarantee that the data is reliably stored. In fact, given the required large number of storage servers, server failures happen on a daily basis. To prevent from data loss, redundant data is stored alongside the initial data, by either replicating or encoding the data. The amount of redundant data is referred to as the storage overhead. While, for the same failure tolerance, encoding the data requires a smaller storage overhead than replicating the data, it implies a more complex repair process of the failed servers. Therefore, on top of the storage overhead and the failure tolerance, two notions are of particular interest: the repair bandwidth and the locality, which is the number of servers contacted for repairing a few failed servers. This thesis focuses on the notion of locality. More precisely, the main goal is to derive a tradeoff between the storage overhead, the failure tolerance, and the locality when the underlying code alphabet is fixed. Deriving a tradeoff is important in practice as it characterizes the best possible codes. Furthermore, since the alphabet relates to the repair complexity and affects the different aforementioned notions, it is interesting to derive alphabet-dependent tradeoffs. To approach this problem, we use the internal structure of the storage codes and the relation between codes and matroids. Matroids are interesting mathematical objects on their own right and provide useful tools related to the alphabet. In the articles composing this thesis, we derive alphabet-dependent tradeoffs with various locality assumptions. Furthermore, we study the impact of the alphabet on the substructures of a representable matroid. We also analyse the hierarchical locality of a specific code construction. Finally, we examine nonlinear codes with locality on mixed alphabets and derive their tradeoff using polymatroids.