Learning Centre

On Matroid Theory and Distributed Data Storage

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.advisor Hollanti, Camilla, Prof., Aalto University, Department of Mathematics and Systems Analysis, Finland
dc.contributor.advisor Freij-Hollanti, Ragnar, Dr., Aalto University, Department of Mathematics and Systems Analysis, Finland
dc.contributor.advisor Westerbäck, Thomas, Dr., Mälardalen University, Sweden
dc.contributor.author Grezet, Matthias
dc.date.accessioned 2019-10-15T09:01:24Z
dc.date.available 2019-10-15T09:01:24Z
dc.date.issued 2019
dc.identifier.isbn 978-952-60-8711-5 (electronic)
dc.identifier.isbn 978-952-60-8710-8 (printed)
dc.identifier.issn 1799-4942 (electronic)
dc.identifier.issn 1799-4934 (printed)
dc.identifier.issn 1799-4934 (ISSN-L)
dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/40735
dc.description.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. en
dc.format.extent 69 + app. 105
dc.format.mimetype application/pdf en
dc.language.iso en en
dc.publisher Aalto University en
dc.publisher Aalto-yliopisto fi
dc.relation.ispartofseries Aalto University publication series DOCTORAL DISSERTATIONS en
dc.relation.ispartofseries 163/2019
dc.relation.haspart [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.
dc.relation.haspart [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
dc.relation.haspart [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
dc.relation.haspart [Publication 4]: Matthias Grezet, Camilla Hollanti. The Complete Hierarchical Locality of the Punctured Simplex Code. Submitted to Designs, Codes and Cryptography, 20 pages, 2019.
dc.relation.haspart [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
dc.relation.haspart [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.
dc.relation.haspart [Errata file]: Errata of P. 2
dc.subject.other Mathematics en
dc.title On Matroid Theory and Distributed Data Storage en
dc.type G5 Artikkeliväitöskirja fi
dc.contributor.school Perustieteiden korkeakoulu fi
dc.contributor.school School of Science en
dc.contributor.department Matematiikan ja systeemianalyysin laitos fi
dc.contributor.department Department of Mathematics and Systems Analysis en
dc.subject.keyword storage systems en
dc.subject.keyword matroids en
dc.subject.keyword information-theoretic bounds en
dc.subject.keyword locally repairable codes en
dc.subject.keyword cyclic flats en
dc.subject.keyword polymatroids en
dc.identifier.urn URN:ISBN:978-952-60-8711-5
dc.type.dcmitype text en
dc.type.ontasot Doctoral dissertation (article-based) en
dc.type.ontasot Väitöskirja (artikkeli) fi
dc.contributor.supervisor Hollanti, Camilla, Prof., Aalto University, Department of Mathematics and Systems Analysis, Finland
dc.opn Britz Thomas, Dr., University of New South Wales, Australia
dc.contributor.lab Algebra, Number Theory, and Applications en
dc.rev Whittle, Geoff, Prof., Victoria University of Wellington, New Zealand
dc.rev Jurrius, Relinde, Dr., Netherlands Defence Academy, Netherlands
dc.date.defence 2019-10-17
local.aalto.acrisexportstatus checked 2019-11-30_1553
local.aalto.formfolder 2019_10_15_klo_11_35
local.aalto.archive yes

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search archive

Advanced Search

article-iconSubmit a publication