CIF: Small: Collaborative Research: Leveraging Data Popularity in Distributed Storage Systems via Constrained Design Theory

Arizona State University, Scottsdale AZ

Investigators

Abstract

Recent years have witnessed a surge of large-scale distributed storage system implementations and accompanying data analyses and coding methods that enable their reliable, secure and low-delay operation. Nevertheless, in many system studies, important data demand (popularity) features which have a strong bearing on system access control, private information retrieval and computational complexity have been largely overlooked. This can be attributed in part to the fact that most cloud storage facilities employ different storage platforms for hot and cold data, thereby partly addressing problems associated with variable data demands. But even within the hot and cold data categories there exist significant variations in data popularity that create many nontrivial system design challenges. To address these issues, the proposed research program aims to develop a new family of mathematical objects termed constrained designs and Steiner systems in particular. Designs represent finite collections of subsets of a ground set whose elements satisfy predefined symmetry constraints with respect to set intersections and arrangements. Elements of a design are associated with data chunks, while subsets of elements represent data chunks to be stored on the same disk or server; given their simplicity and rich mathematical structure, designs have been used with great success in many practical distributed storage system platforms. In the presence of nonuniform demands for objects and data files, intersection constraints alone fail to ensure underlying implementation constraints. Consequently, elements have to be equipped with nonnegative popularity values, and the underlying combinatorial designs modified to satisfy additional algebraic and frequency constraints enforced by data popularity values. This new model leads to a unique collection of challenging mathematical problems regarding constructions of weighted and labeled combinatorial designs. Particular problems to be considered include developing designs for balanced server access, private information retrieval in the presence of popularity side information and transversal designs for labeled batch codes. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.