Maximal Achievable Service Rates of Codes and Connections to Combinatorial Designs

Ly, Hoang; Soljanin, Emina

Permalink

https://hdl.handle.net/2142/130255 Copy

Description

Title

Maximal Achievable Service Rates of Codes and Connections to Combinatorial Designs

Author(s)

• Ly, Hoang
• Soljanin, Emina

Issue Date

2025-09-17

Keyword(s)

• Service rate regions
• Distributed storage systems
• Combinatorial design theory
• Majority-logic decoding

Abstract

We investigate the service-rate region (SRR) of distributed storage systems that employ linear codes. We focus on systems where each server stores one code symbol, and a user recovers a data symbol by accessing any of its recovery groups, subject to per-server capacity limits. The SRR–the convex polytope of simultaneously achievable request rates–captures system throughput and scalability. We first derive upper and lower bounds on the maximum request rate of each data object. These bounds hold for all linear codes and depend only on the number of parity checks orthogonal to a particular set of codeword coordinates associated with that object, i.e., the equations used in majority-logic decoding, and on code parameters. We then check the bound saturation for 1) all non-systematic codes whose SRRs are already known and 2) systematic codes. For the former, we prove the bounds are tight. For systematic codes, we show that the upper bound is achieved whenever the supports of minimum-weight dual codewords form a 2-design. As an application, we determine the exact per-object demand limits for Hamming codes. Our framework offers a new perspective on addressing the SRR problem through the lens of combinatorial design theory.

Publisher

Allerton Conference on Communication, Control, and Computing

Series/Report Name or Number

2025 61st Allerton Conference on Communication, Control, and Computing Proceedings

ISSN

2836-4503

Type of Resource

Text

Genre of Resource

Conference Paper/Presentation

Language

eng

Handle URL

https://hdl.handle.net/2142/130255&&

Copyright and License Information

Copyright 2025 is held by Hoang Ly and Emina Soljanin.

Owning Collections