On the Service Rate Region of Reed–Muller Codes
Hoang Ly, Emina Soljanin, V. Lalitha · 2025
Read On the Service Rate Region of Reed–Muller Codes by Hoang Ly, Emina Soljanin, V. Lalitha (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-2501-13105.txt.
Introduction
Hoang Ly, Emina Soljanin, and Lalitha study how fast a stored data system can serve requests, in a 2025 paper. The system uses Reed-Muller codes, a known way to store data with built-in backup. The set of rates the system can handle forms a shape that shows its limits. Knowing that shape helps judge how well the system scales.
Using the geometry of the codes, the authors map the sets of servers that can rebuild each data item. They show those sets link to light codewords in a paired code. From that link, they derive tight bounds on the top rate for each item. The bounds pin down the rate region with a close fit from both sides.
Catalog record
| CREATOR | Hoang Ly, Emina Soljanin, V. Lalitha |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 107 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-13105
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the Service Rate Region of Reed–Muller Codes Hoang Ly, Emina Soljanin, V. Lalitha Abstract We study the Service Rate Region of Reed–Muller codes in the context of distributed storage systems. The service rate region is a convex polytope comprising all achievable data access request rates under a given coding scheme. It represents a critical metric for evaluating system efficiency and scalability. Using the geometric properties of Reed–Muller codes, we characterize recovery sets for data objects, including their existence, uniqueness, and enumeration. This analysis reveals a connection between recovery sets and minimum-weight codewords in the dual Reed–Muller code, providing a framework for identifying those recovery sets. Leveraging these results, we derive explicit and tight bounds on the maximal achievable demand for individual data objects, thereby defining the maximal simplex contained within the service rate region, and the smallest simplex containing it. These two simplices provide a tight approximation to the service-rate region of Reed–Muller codes. I Introduction Modern computing systems depend on efficient data access from their underlying storage layers to deliver high overall performance. To ensure reliability and balance server load, storage systems commonly replicate data objects across multiple nodes. The level of replication typically reflects the expected demand for each object. However, in modern systems, such as edge computing, access patterns are often skewed and can frequently change [ 1 , 2 ] . In such settings, redundancy schemes that incorporate erasure coding are expected to be more effective than replication alone [ 3 ] . With the advent of distributed storage, various new performance metrics have emerged. In addition to the standard high fault-tolerance and low overhead, codes should provide efficient maintenance by, e.g., keeping the required repair bandwidth low or the size of repair groups small [ 4 ] . The Service Rate Region (SRR) has emerged as a fundamental metric for evaluating the efficiency and scalability of data access in coded distributed storage systems, thereby generalizing the earlier notion of availability [ 3 ] . SRR is defined as the set of all simultaneously supportable data access request rates under a given redundancy scheme. The SRR is a convex polytope in \mathbb{R}^{k} , where k is the number of distinct data objects in the system. This polytope offers a precise characterization of the system’s throughput capabilities [ 3 ] . Recent work has analyzed the SRR for several families of linear codes. In particular, explicit descriptions of the SRR of binary Simplex codes, first-order Reed–Muller codes [ 5 ] , and Hamming codes [ 6 , 7 ] have been presented. A notable insight from [ 8 ] links the integrality of SRR demand vectors to batch codes, showing a one-to-one correspondence between integral SRRs and batch coding schemes. Authors in [ 3 ] investigate the geometric attributes of SRR polytopes, while authors in [ 7 ] have demonstrated the theoretical relationship connecting SRR to both combinatorial design theory and majority-logic decoding [ 9 ] . More broadly, the SRR framework generalizes classical load balancing [ 10 ] , and has been connected to majority-logic decoding, combinatorial design theory, and the incidence pattern of minimum-weight dual codewords—that is, how the supports of these codewords intersect across coordinate positions [ 7 ] . Collectively, these results underscore the utility of linear codes in optimizing data access. Maximum distance separable (MDS) codes are particularly notable for achieving the optimal trade-off between redundancy and reliability [ 11 , 12 ] . Their SRRs have been rigorously analyzed under systematic encoding [ 3 ] , where a water-filling allocation scheme was shown to be optimal. These results were later refined and generalized in [ 13 ] . Furthermore, the authors of [ 14 ] studied various geometric properties of SRR polytopes of general linear codes, including their volumes. Given these developments, a natural next step is to investigate the SRRs of other code families with rich algebraic structure—most notably higher-order Reed–Muller (RM) codes, whose SRRs remain largely uncharacterized. Although many storage allocation problems can be reformulated as hypergraph matching problems [ 15 ] and solved using linear programming relaxations [ 16 ] , these techniques become challenging to apply when the underlying graph structure associated with data/symbol recovery is highly complex or is not explicitly known. RM codes, despite their elegant algebraic construction, induce intricate, only partially understood geometric structures that significantly complicate SRR analysis [ 17 ] . RM codes were introduced in 1954 by Muller [ 18 ] , and shortly thereafter Reed proposed a majority-logic algorithm [ 19 ] . Recently, RM codes have gained renewed attention for their capacity-achieving performance over binary symmetric and erasure channels [ 20 , 21 , 22 ] . Their applications span beyond communication—appearing in 5G NR [ 23 ] , compressed sensing [ 24 ] , private information retrieval [ 25 ] , and quantum computation [ 26 ] . In the context of SRR, their utility comes from the abundance of disjoint recovery sets (also called repair groups) per message symbol, as revealed by Reed’s decoding algorithm, and their rich geometric structure [ 27 ] . Our main contribution is a rigorous analysis of the SRR for RM codes of arbitrary parameters. Leveraging the correspondence between RM codes and finite Euclidean geometry, we first characterize the recovery sets for data objects, establishing their existence, uniqueness, and enumeration. This analysis reveals a fundamental link between recovery sets and minimum-weight codewords in the dual code, providing a framework that generalizes Reed’s classical majority-logic decoding. Building on these geometric insights, we derive explicit, tight bounds on the maximal achievable demand for individual data objects. To address the complexity of the full SRR polytope, we construct a “maximal achievable simplex” (inner bound) and a tight “enclosing simplex” (outer bound), proving that the latter is at most a factor of 2 larger than the former. This provides a tight approximation of the service region even where a complete characterization is analytically intractable. We substantiate this intractability by establishing an equivalence between listing all recovery sets and the coordinate-constrained weight enumerator problem —enumerating all codewords in the dual RM code constrained to specific values at specific indices. Since the enumerator problem (and related problems such as determining higher-order Hamming weights) remains unsolved for general parameters, enumerating recovery sets is generally impossible. Consequently, characterizing the exact SRR remains an open challenge, making our tight approximation results particularly significant. Paper Organization. Section II defines the SRR in coded storage systems, introduces the recovery graph, and explains how the SRR problem can be reframed into a graph-theoretic one. Section III reviews the properties of the Reed-Muller code essential for data recovery analysis. Section IV presents the main results on recovery sets, including their enumeration and connections to dual codewords. Section V derives explicit SRR bounds for RM codes using the results established earlier. Section VI concludes the paper. Nomenclatures and Notations This section introduces the notation used throughout the paper. Concepts that are well-known in the literature will be emphasized the first time in italic , whereas less standard concepts are formally introduced via Definition . Matrices and standard basis vectors are denoted in boldface . \mathbb{N},\mathbb{R} denote the set of nonnegative integers and real numbers, respectively.