Maximal Achievable Service Rates of Codes and Connections to Combinatorial Designs

Hoang Ly and Emina Soljanin · 2025

Read Maximal Achievable Service Rates of Codes and Connections to Combinatorial Designs by 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-2506-16983.txt.

Introduction

Hoang Ly and Emina Soljanin study how fast a coded storage system can serve data, in a 2025 math paper. In such a system, each server holds one coded piece of a file. A user can rebuild a data piece from any of several server groups. Each server can only handle so many requests at once.

The set of request rates a system can meet at once forms a shape called the service-rate region. The authors bound the top rate for each data piece in any linear code. The bounds rest on how many checks can decode that piece and on basic code traits. They prove the bounds are tight for many known codes. For a wide class of codes, the bound holds when dual codeword supports form a 2-design. They also pin down exact limits for binary Hamming codes.

Catalog record

CREATORHoang Ly and Emina Soljanin
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE44 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-16983

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Maximal Achievable Service Rates of Codes and Connections to Combinatorial Designs Hoang Ly and Emina Soljanin 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 binary Hamming codes. Our framework provides a new lens to address the SRR problem through combinatorial design theory. E-mail: {mh.ly, emina.soljanin}@rutgers.edu I Introduction Reliable and scalable data access is a key requirement in modern computing systems, particularly under dynamic and uneven demands. Traditional systems have relied mainly on basic replication strategies [ 1 ] . The increasing disparity in data popularity has motivated hybrid redundancy schemes that combine erasure coding with replication. In this context, Service Rate Region (SRR) has emerged as a foundational metric, quantifying the set of achievable request rates supported by a given redundancy configuration [ 1 , 2 ] . The concept of SRR is closely related to load-balancing [ 3 ] , and it generalizes the problem of batch codes [ 4 ] . It is also connected to the problem of access balancing; see, e.g., [ 5 ] and the follow-up work. Previous work has largely characterized the SRRs of several important code families, including MDS, Simplex, first- and higher-order Reed-Muller codes, and locally recoverable codes; see [ 1 ] , and more recently [ 6 , 7 ] . At the same time, other studies investigated code parameters, such as the field size and block length required for a target SRR [ 8 ] . Despite these developments, many fundamental questions about the behavior and structure of the SRR remain open. In distributed storage systems and SRR problems, each data object is retrieved through recovery sets (or repair groups), which are collections of stored symbols that together enable the reconstruction of the desired object. This notion closely parallels that of majority-logic decoding (MLD) in linear codes, where each message (or information) symbol is recovered using multiple (not necessarily disjoint) sets of codeword symbols. Each such set contributes a "vote" toward the true value of the message symbol, and decoding succeeds if the majority of these votes remain uncorrupted in the presence of noise in the communication channel. Since errors in received codeword symbols affect all recovery sets that contain them, the effectiveness of MLD depends critically on the overlap structure among these sets. The codes that can be decoded using this scheme are known as majority-logic decodable codes . These codes are attractive in practice due to their inexpensive decoding circuitry and their potential to correct beyond their worst-case error bounds [ 9 ] . The structure of the recovery sets–and thus the correction capability of MLD–is intimately tied to the combinatorics of the dual code, specifically to how codeword symbols appear in the supports of dual codewords. A fundamental result of Rudolph [ 10 ] characterizes the error correction capability of MLD in a code when the supports of its dual codewords exhibit certain combinatorial regularities. For some extensions of these results, see, for instance, [ 11 , 12 ] . This paper explicitly connects SRR analysis with MLD decoding and combinatorial design theory. We thus reveal how a linear code’s combinatorial structure and error-correcting properties fundamentally influence its data access performance in storage systems. The rest of the paper is organized as follows. Section II formally presents the problem setting, defines the SRR problem and maximal achievable demand for each data object, and summarizes our main contributions. Section III introduces majority-logic decoding and establishes bounds on the maximal achievable demand using orthogonal parity checks. In Section IV, we specialize these results into systematic codes and identify the conditions under which the upper bound is achieved, drawing connections to combinatorial designs. Section V concludes the paper. II Problem Statement In this section, we first introduce the notation used throughout the paper, followed by basic definitions and relevant results from combinatorial design theory. The results we include are classical and well known, and can be found in standard references such as [ 13 ] . We then formally describe and formulate the SRR problem, and maximal achievable demands of data objects, and conclude with a summary of the main results. II-A Preliminaries and Notation The finite field over a prime or prime power q is denoted as \mathbb{F}_{q} . A q -ary linear code \mathcal{C} with parameters [n,k,d]_{q} is a k -dimensional subspace with minimum (Hamming) distance d of the n -dimensional vector space \mathbb{F}_{q}^{n} . Also, d^{\perp} denotes the dual distance, i.e., minimum distance of the dual code \mathcal{C}^{\perp} . Hamming weight of a codeword \boldsymbol{x} is denoted as \textsf{w}(\boldsymbol{x}) . The symbols \boldsymbol{0}_{k} and \boldsymbol{1}_{k} denote the all-zero and all-one column vectors of length k , respectively. Standard basis (column) vector with a one at position i and 0s elsewhere is represented by \boldsymbol{e}_{i} . Moreover, \boldsymbol{c}^{j}(\boldsymbol{G}) and \boldsymbol{h}^{i}(\boldsymbol{G}) denote respectively the j -th column and the i -th row of the matrix \boldsymbol{G} being considered, and \boldsymbol{G} can be dropped when the context is clear. \mathrm{Supp}(\boldsymbol{x}) denotes the support of a codeword \boldsymbol{x} , and x_{j} its j -th coordinate. The set of positive integers not exceeding i is denoted as [i] . Similarly, [a,b] represents the set of integers between a and b , where a,b\in\mathbb{N} and a<b . The cardinality of a finite set V is |V| . A pair (V,\mathcal{A}) is called a t\text{--}(n,k,\lambda) block design (or simply, a t -design) if it satisfies the following: V is a set of n elements (called points ), and \mathcal{A} is a collection of k -element subsets of V (called blocks ), such that every t -subset of V is contained in exactly \lambda blocks in \mathcal{A} . A Steiner system is a t - (n,k,\lambda) block design with t=2,\,\lambda=1 . A fundamental result involving designs is the "Lower-order balance": Lemma 1 . (Lower-order balance; see, e.g., [ 13 , Corollary 9.6] ) Suppose that (V,\mathcal{A}) is a t -design, and 1\leq s\leq t . Then (V,\mathcal{A}) is a s -design. That is, any t -design is automatically balanced at all lower levels, in particular it is always a (t-1) -design. II-B Service Rate of Codes Consider a storage system in which k data objects o_{1},\ldots,o_{k} are stored on n servers, labeled 1,\ldots,n , using a linear [n,k]_{q} code

Read the complete text