2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | M.1.5 | ||
| Paper Title | Access Balancing in Storage Systems by Labeling Partial Steiner Systems | ||
| Authors | Yeow Meng Chee, National University of Singapore, Singapore; Charles J. Colbourn, Arizona State University, United States; Son Hoang Dau, RMIT University, Australia; Ryan Gabrys, University of Illinois at Urbana-Champaign (UIUC), United States; Alan C. H. Ling, University of Vermont, United States; Dylan Lusi, Arizona State University, United States; Olgica Milenkovic, University of Illinois at Urbana-Champaign (UIUC), United States | ||
| Session | M.1: Codes for Distributed Storage I | ||
| Presentation | Lecture | ||
| Track | Coding for Storage and Memories | ||
| Manuscript | Click here to download the manuscript | ||
| Virtual Presentation | Click here to watch in the Virtual Symposium | ||
| Abstract | Storage architectures ranging from minimum bandwidth regenerating encoded distributed storage systems to declustered-parity RAIDs can employ dense partial Steiner systems to support fast reads, writes, and recovery of failed storage units. To enhance performance, popularities of the data items should be taken into account to make frequencies of accesses to storage units as uniform as possible. A combinatorial model ranks items by popularity and assigns data items to elements in a dense partial Steiner system so that the sums of ranks of the elements in each block are as equal as possible. By developing necessary conditions in terms of independent sets, we demonstrate that certain Steiner systems must have a much larger difference between the largest and smallest block sums than is dictated by an elementary lower bound. In contrast, we also show that certain dense partial S(t; t+1; v) designs can be labeled to realize the elementary lower bound. Furthermore, we prove that for every admissible order v, there is a Steiner triple system (S(2; 3; v)) whose largest difference in block sums is within an additive constant of the lower bound. A full version [1] of this paper is accessible at: https://arxiv.org/abs/1906.12073. | ||
Plan Ahead
2021 IEEE International Symposium on Information Theory
11-16 July 2021 | Melbourne, Victoria, Australia
