On the Service Rate Region of Reed-Muller Codes
Authors:
- 22 June 2025
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-6
Abstract
We study the Service Rate Region (SRR) of distributed storage systems that store data using Reed-Muller (RM) codes. We focus on systems where each server stores an RM codeword symbol, and each user aims to decode a single data symbol by accessing the servers storing one of the data symbol's recovery groups. The cumulative access rate to each server cannot exceed its given service rate. The SRR is a convex polytope comprising all achievable data access request rates. It represents a critical metric for evaluating system efficiency and scalability. We characterize recovery sets for data objects using the geometric properties of RM codes. This analysis reveals a connection between the RM code's recovery sets and minimumweight codewords in the dual RM code. Using these results, we derive explicit and tight bounds for the maximal achievable demand for individual data objects, which define the maximal simplex polytope within the service rate region.Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- On the Service Rate Region of Reed-Muller Codes2025
- On the Parameters of Codes for Data Access2024
- A proof that Reed-Muller codes achieve Shannon capacity on symmetric channels2023
- A Geometric View of the Service Rates of Codes Problem and its Application to the Service Rate of the First Order Reed-Muller Codes2020
- Reed–Muller Codes Achieve Capacity on Erasure ChannelsIEEE Transactions on Information Theory, 2017
- Construction of a Large Class of Deterministic Sensing Matrices That Satisfy a Statistical Isometry PropertyIEEE Journal of Selected Topics in Signal Processing, 2010
- The second weight of generalized Reed-Muller codes in most casesCryptography and Communications, 2009
- 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