Technical Program

Paper Detail

Paper IDM.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:

Plan Ahead


2021 IEEE International Symposium on Information Theory

11-16 July 2021 | Melbourne, Victoria, Australia

Visit Website!