Service Rate Regions of MDS Codes and Fractional Matchings in Quasi-uniform Hypergraphs
Hoang Ly, Emina Soljanin, Hoang Ly and Emina Soljanin · 2025
Read Service Rate Regions of MDS Codes and Fractional Matchings in Quasi-uniform Hypergraphs by Hoang Ly, Emina Soljanin, Hoang Ly and Emina Soljanin (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-17244.txt.
Introduction
Hoang Ly and Emina Soljanin analyze how redundantly stored data systems serve many users at once in this two thousand twenty-five paper. The service rate region captures that ability as a geometric object, a polytope whose dimensions are the request rates for each stored object. The authors focus on systems using a class of maximum distance separable codes. For each code they characterize the region's intercepts and the smallest standard simplex containing it.
A graph-theoretic framework connects the problem to fractional matchings in quasi-uniform hypergraphs. Finding the service rate region becomes equivalent to computing an image of the fractional matching polytope. The authors introduce greedy matchings and show attention can be restricted to them, then determine the region for a large subset of the codes. The results unify earlier characterizations of systematic and non-systematic systems.
Catalog record
| CREATOR | Hoang Ly, Emina Soljanin, Hoang Ly and Emina Soljanin |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 96 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-17244
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Service Rate Regions of MDS Codes and Fractional Matchings in Quasi-uniform Hypergraphs Hoang Ly, Emina Soljanin, Hoang Ly and Emina Soljanin 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 ℝ k \mathbb{R}^{k} , where each axis corresponds to the request rate for one of k 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. I Introduction Erasure-coded distributed storage systems provide reliability and availability by storing encoded data objects across multiple servers. Redundancy not only protects against node failures but also mitigates performance degradation in download times caused by stragglers (slow or unresponsive servers). Previous research has primarily focused on optimizing storage efficiency by minimizing redundancy overhead and improving recovery efficiency of lost data through reduced repair bandwidth or repair degree [ 1 ] . Another line of work focuses on the download-time performance evaluation of distributed storage systems [ 2 , 3 ] . Evaluating download time is challenging because coded systems introduce complex data-access queues [ 4 ] . Even in simple cases, one has to resort to heuristics [ 5 ] . The stability regions of these queues, known as the service rate region (SRR), have emerged as a fundamental metric for evaluating the performance of erasure-coded distributed storage systems [ 6 ] . For a system that stores k data objects redundantly on n servers, each capable of handling requests at a rate \mu , we define the SRR as the set of request rate vectors (\lambda_{1},\dots,\lambda_{k}) that the system can serve concurrently without exceeding the capacity of any server. Geometrically, the SRR forms a convex polytope in \mathbb{R}^{k} , with each axis corresponding to the request rate for a distinct data object [ 7 ] . Recent work has focused on characterizing SRRs under various coding schemes. The exact SRRs are known for Simplex codes [ 7 ] , Hamming codes [ 8 , 9 ] , certain structured MDS codes [ 6 , 10 ] , and for Reed-Muller codes of first-order and general (higher orders) [ 11 , 12 , 13 ] . The general properties of SRR polytopes have been explored in [ 14 ] , and connections to the majority-logic decoding and combinatorial design theory have also been established [ 9 ] . Parallel research has examined the code design problem: constructing codes whose SRRs meet specific performance or structural constraints [ 15 ] . This paper characterizes the SRRs of a broad class of MDS codes, which remain central to both practical deployments and theoretical analyses of erasure-coded systems. Building on a graph-theoretic foundation, we extend prior frameworks to methodically analyze MDS codes with varying numbers of systematic (uncoded) and coded server nodes. Our approach leverages fractional matchings in hypergraphs to expose new structural insights into the geometry of SRRs. Distributed storage allocation problems are often reformulated as hypergraph matching problems, where recovery sets correspond to hyperedges [ 16 , 17 ] . These formulations lend themselves to efficient relaxation via fractional matchings, enabling linear programming techniques for performance analysis and optimization. However, in practice, these problems often become computationally intractable due to the high degree of overlap among hyperedges or the inherent complexity of identifying all such recovery sets [ 13 ] . Such structural challenges motivate the need for more refined combinatorial approaches to understanding and characterizing the underlying SRR. We here leverage the concept of recovery hypergraphs , first defined in [ 10 ] , to translate the problem of analyzing SRRs into an equivalent graph-theoretic problem. We derive explicit geometric inner and outer bounds for these regions, providing clear insights into how different storage strategies directly influence the SRR. In particular, by analyzing these recovery hypergraphs, we prove that increasing the number of systematic servers enlarges the SRR, highlighting a fundamental trade-off between simplicity and flexibility in data service. Moreover, we introduce a novel data request allocation strategy called Greedy Matching and establish its optimality, i.e., that it suffices to focus on these matchings to characterize the SRR rather than all possible fractional matchings. Utilizing this strategy, we explicitly characterize SRRs across various system configurations, generalizing and refining existing results. Our findings offer a rigorous foundation for understanding and optimizing data service capabilities in distributed storage systems, paving the way for superior system design and more efficient data access strategies. The remainder of the paper is organized as follows. Section II first introduces the redundant storage model and formally defines service rate region (SRR) of distributed storage systems. It then reformulates the problem in graph-theoretic and linear programming terms and introduces relevant combinatorial concepts and tools. Section III derives two geometric bounds for SRRs. Section IV uses the derived bounds to establish an inclusion theorem for SRRs, proving that SRRs strictly expand as the number of systematic nodes increases. In Section V , we propose a novel Greedy Matching allocation strategy and prove its optimality. Section VI explicitly characterizes the SRRs in various configurations of the system. Finally, Section VII concludes the paper and outlines potential directions for future research. II Problem Formulation We first describe a redundant storage model consisting of n identical nodes (servers) that collectively store multiple data objects with redundancy. We then construct a family of underlying MDS generator matrices that govern how data objects are encoded and distributed across these servers. Finally, we introduce certain concepts necessary for our analysis. When mentioning well-known concepts in the literature, we use italic . We formally introduce the new and less standard concepts through a Definition . The matrices and standard basis vectors are denoted in bold . The finite field over a prime power q is denoted by \mathbb{F}_{q} . A linear code \mathcal{C} on \mathbb{F}_{q} with parameters [n,k,d]_{q} , is a k -dimensional subspace of the n -dimensional vector space \mathbb{F}_{q}^{n} with a minimum Hamming distance d . The symbols \boldsymbol{0}_{k} and \boldsymbol{1}_{k} denote the all-zero and all-one column vectors of length k , respectively. The standard basis (column) vector with a one at position i and zero elsewhere is represented by \boldsymbol{e}_{i} , and its transpose by \boldsymbol{e}_{i}^{\top} . The set of positive integers not exceeding i , which is \{1,2,\dots,i\} , is denoted [i] . Finally, (x)^{+}=\max\{x,0\} for any real