On Matroid Theory and Distributed Data Storage

Thumbnail Image
Files
isbn9789526087115.pdf (5.9 MB)

Errata_grezet_matthias_DD_163_2019_publication_P2.pdf (102.02 KB)
Journal Title
Journal ISSN
Volume Title
School of Science | Doctoral thesis (article-based) | Defence date: 2019-10-17
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Author
Date
2019
Department
Matematiikan ja systeemianalyysin laitos
Department of Mathematics and Systems Analysis
Major/Subject
Mcode
Degree programme
Language
en
Pages
69 + app. 105
Series
Aalto University publication series DOCTORAL DISSERTATIONS, 163/2019
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.
Description
Supervising professor
Hollanti, Camilla, Prof., Aalto University, Department of Mathematics and Systems Analysis, Finland
Thesis advisor
Hollanti, Camilla, Prof., Aalto University, Department of Mathematics and Systems Analysis, Finland
Freij-Hollanti, Ragnar, Dr., Aalto University, Department of Mathematics and Systems Analysis, Finland
Westerbäck, Thomas, Dr., Mälardalen University, Sweden
Keywords
storage systems, matroids, information-theoretic bounds, locally repairable codes, cyclic flats, polymatroids
Other note
Parts
  • [Publication 1]: Ragnar Freij-Hollanti, Matthias Grezet, Camilla Hollanti, Thomas Westerbäck. Cyclic Flats of Binary Matroids. Submitted to Journal of Combinatorial Theory, Series B, 2019, 41 pages.
  • [Publication 2]: Matthias Grezet, Ragnar Freij-Hollanti, Thomas Westerbäck, Oktay Olmez, Camilla Hollanti. Bounds on Binary Locally Repairable Codes Tolerating Multiple Erasures. In The International Zurich Seminar on Information and Communication, pp. 103–107, 2018.
    Full text in Acris/Aaltodoc: http://urn.fi/URN:NBN:fi:aalto-201804042054
    DOI: 10.3929/ethz-b-000245075 View at publisher
  • [Publication 3]: Matthias Grezet, Ragnar Freij-Hollanti, Thomas Westerbäck, Camilla Hollanti. Alphabet-Dependent Bounds for Linear Locally Repairable Codes Based on Residual Codes. Accepted for publication in IEEE Transactions on Information Theory, 2019, 12 pages. Full Text in Acris/Aaltodoc: http://urn.fi/URN:NBN:fi:aalto-201909205356.
    DOI: 10.1109/TIT.2019.2911595 View at publisher
  • [Publication 4]: Matthias Grezet, Camilla Hollanti. The Complete Hierarchical Locality of the Punctured Simplex Code. Submitted to Designs, Codes and Cryptography, 20 pages, 2019.
  • [Publication 5]: Matthias Grezet, Thomas Westerbäck, Ragnar Freij-Hollanti, Camilla Hollanti. Uniform Minors in Maximally Recoverable Codes. IEEE Communications Letters, 2019, Volume 23, Issue 8, pp. 1297–1300.
    DOI: 10.1109/LCOMM.2019.2921540 View at publisher
  • [Publication 6]: Thomas Westerbäck, Matthias Grezet, Ragnar Freij-Hollanti, Camilla Hollanti. On the Polymatroidal Structure of Quasi-Uniform Codes with Applications to Heterogeneous Distributed Storage. In International Symposium on Mathematical Theory of Networks and Systems (MTNS), pp. 641–647, 2018.
  • [Errata file]: Errata of P. 2
Citation
Permanent link to this item
https://urn.fi/URN:ISBN:978-952-60-8711-5
Collections
[diss] Perustieteiden korkeakoulu / SCI