Service Rate Regions of MDS Codes and Fractional Matchings in Quasi-Uniform Hypergraphs
Top Cited Papers
- 6 February 2026
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 72 (4) , 2144-2161
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.Keywords
All Related Versions
Funding Information
- National Science Foundation (CIF-2122400)
This publication has 17 references indexed in Scilit:
- On the Service Rate Region of Reed-Muller Codes2025
- On the Parameters of Codes for Data Access2024
- Dual-Code Bounds on Multiple Concurrent (Local) Data Recovery2022
- A Geometric View of the Service Rates of Codes Problem and its Application to the Service Rate of the First Order Reed-Muller Codes2020
- A Combinatorial View of the Service Rates of Codes Problem, its Equivalence to Fractional Matching and its Connection with Batch Codes2020
- Heuristics for Analyzing Download Time in MDS Coded Storage Systems2018
- On the service capacity region of accessing erasure coded content2017
- Analyzing the download time of availability codes2015
- Large matchings in uniform hypergraphs and the conjectures of Erdős and SamuelsJournal of Combinatorial Theory, Series A, 2012
- Systematic MDS Erasure Codes Based on Vandermonde MatricesIEEE Communications Letters, 2004