Abstract
The Service Rate Region (SRR) is a fundamental performance metric for distributed storage systems with redundancy, quantifying the range of data request patterns that the system can serve concurrently without exceeding the servers’ capacities. Geometrically, the SRR is a convex polytope in $\mathbb {R}^{k}$ , where each axis corresponds to the request rate for one of $k$ data objects. This paper focuses on the SRR of systems encoded using a large class of Maximum Distance Separable (MDS) codes. We characterize the axial intercepts of the SRR and derive the smallest standard simplex containing it, demonstrating that the SRR expands strictly as the number of systematic columns in the generator matrix of the code increases. To facilitate this analysis, we develop a graph-theoretic framework that models the SRR as the image of a fractional matching polytope of a quasi-uniform hypergraph. We introduce a novel allocation strategy, Greedy Matching, and use it to characterize the SRRs without requiring an exhaustive evaluation of fractional matchings. These findings yield exact SRRs for a wide range of MDS codes and unify previous results regarding systematic and non-systematic constructions. Our work offers both theoretical and practical guidance for designing storage systems with optimized data service.
Funding Information
  • National Science Foundation (CIF-2122400)