On the Polymatroidal Structure of Quasi-Uniform Codes with Applications to Heterogeneous Distributed Storage
Thomas Westerbäck, Matthias Grezet, Ragnar Freij-Hollanti, Camilla Hollanti · mediaTUM – the media and publications repository of the Technical University Munich (Technical University Munich) · 2018
Recent research on distributed storage systems (DSSs) has revealed interesting connections between locally repairable codes (LRCs) and their associated matroids and polymatroids.In this paper we define L-polymatroids -polymatroids with an added length function -in order to consider completely general LRCs in that they are defined as subsets ofwhere each Ai is some arbitrary finite set.Earlier research in this area has only considered codes over non-mixed alphabets, i.e., A1 = • • • = An.We generalize the notions of locality and availability to Lpolymatroids, and a Singleton-type bound for L-polymatroids is given.This result implies a corresponding bound on LRCs and generalizes earlier Singleton-type bounds given on LRCs.Moreover, the necessary structural conditions are given for L-polymatroids achieving the bound, yielding also the corresponding necessary conditions for LRCs.Finally, implications of our results for quasi-uniform codes and in particular quasiuniform codes from a construction built on cosets of groups are examined.