Upper bounds on data access rates for coded distributed storage systems
Bounds on the Service Rates of Linear Codes and their Connections to Combinatorial Designs
Information Theory
Summary
Distributed storage systems keep data across many servers to protect against loss and improve access. The authors study how much data can be served at once without overloading any server when data is stored using special linear codes. They find new upper limits on how many requests for multiple data pieces can be handled simultaneously based on code properties. This helps understand the efficiency of redundancy in real systems and when these limits can actually be reached.
What this means in practice
- •For network schedulers: Determine the maximum simultaneous data requests a distributed storage system with linear coding can handle without overloading servers.
- •For data center architects: Use code family-specific bounds to design storage layouts that optimize concurrent data access rates.
Authors
Monika Yadav, Priyanka Choudhary, Maheshanand Bhaintwal
Abstract
The service rate region of a distributed storage system describes the set of concurrent demand vectors that can be served without overloading any individual server, and is a fundamental measure of how effectively redundancy is used. In this paper, we investigate aggregate service rates in distributed data storage systems based on linear codes over arbitrary finite fields. We first derive an upper bound on the aggregate service rate for an arbitrary subset of $t$ data objects in terms of the dual distance and the sizes of their smallest recovery sets. For systematic generator matrices, this bound simplifies to an expression depending only on the code length, the dual distance, and the cardinality of the selected subset. This result extends existing bounds and provides a subset-wise formulation of the First Dual Distance Bound. We then establish conditions under which this upper bound is attained. We apply our results to several important families of linear codes, including MDS codes, Reed-Muller codes, constacyclic codes, and extended Golay codes, and obtain exact values of the maximum aggregate service rates for the corresponding subsets of data objects.