On the Service Rate Region of Reed-Muller Codes
Preprint
Abstract
We study the Service Rate Region (SRR) of Reed-Muller (RM) codes in the context of distributed storage systems. The SRR 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 RM 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 RM code, providing a framework for identifying small recovery sets. Using these results, we derive explicit and tight bounds for the maximal achievable demand for individual data objects, which define the maximal simplex within the service rate region.Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- The Service Rate Region PolytopeSIAM Journal on Applied Algebra and Geometry, 2024
- Reed–Muller Codes on BMS Channels Achieve Vanishing Bit-Error Probability for all Rates Below CapacityIEEE Transactions on Information Theory, 2023
- Service Rate Region: A New Aspect of Coded Distributed System DesignIEEE Transactions on Information Theory, 2021
- Reed–Muller Codes: Theory and AlgorithmsIEEE Transactions on Information Theory, 2020
- Reed–Muller Codes Achieve Capacity on Erasure ChannelsIEEE Transactions on Information Theory, 2017
- A Survey on Network Codes for Distributed StorageProceedings of the IEEE, 2011
- Construction of a Large Class of Deterministic Sensing Matrices That Satisfy a Statistical Isometry PropertyIEEE Journal of Selected Topics in Signal Processing, 2010
- General constructions for information-theoretic private information retrievalJournal of Computer and System Sciences, 2005
- A class of multiple-error-correcting codes and the decoding schemeTransactions of the IRE Professional Group on Information Theory, 1954
- Application of Boolean algebra to switching circuit design and to error detectionTransactions of the I.R.E. Professional Group on Electronic Computers, 1954