CS Paper Radar

Recovery Set Structures and Service Rates of Codes Obtained by the Plotkin-type Construction

Priyanka Choudhary, Maheshanand Bhaintwal

cs.IT math.CO ·submitted 2026-10-01 15:47 UTC · v2

Abstract

In distributed storage systems, redundancy enables a single data object to be reconstructed using several disjoint groups of servers. The resulting service rate region (SRR) captures all combinations of object request rates that the system can support simultaneously without overloading any individual server. We analyze the SRR of binary codes obtained via the Plotkin-type construction. We demonstrate that each recovery set for an information object of the Plotkin-type code $\mathcal{C}_p$ induces a corresponding recovery set for the same data object characterized by the underlying code $\mathcal{C}$. Furthermore, by characterizing the recovery sets structure of $\mathcal{C}_p$ in terms of the recovery set structure of $\mathcal{C}$, we identify the additional recovery sets introduced by this construction. Using the associated recovery hypergraphs, we establish bounds on the SRRs of $\mathcal{C}_p$ and iterated code $\mathcal{C}_{p^m}$ in terms of the SRR of $\mathcal{C}$. We consider the family of first-order binary Reed-Muller codes and show how the recovery structure, and consequently, the service rates of R$(1,m)$ for arbitrary $m$ can be recursively derived from a generator matrix of R$(1,2)$ through our results for successive Plotkin-type constructions.

Closest papers

Nearest neighbours by meaning across the whole index.

Bounds on the Service Rates of Linear Codes and their Connections to Combinatorial Designs

cs.IT ·2026-10-19 ·Monika Yadav, Priyanka Choudhary, Maheshanand Bhaintwal
theory similarity 0.66
Abstract

The service rate region of a distributed storage system describes the set of concurrent demand vectors that can be served without overloading any individual server, and is a fundamental measure of how effectively redundancy is used. In this paper, we investigate aggregate service rates in distributed data storage systems based on linear codes over arbitrary finite fields. We first derive an upper bound on the aggregate service rate for an arbitrary subset of $t$ data objects in terms of the dual distance and the sizes of their smallest recovery sets. For systematic generator matrices, this bound simplifies to an expression depending only on the code length, the dual distance, and the cardinality of the selected subset. This result extends existing bounds and provides a subset-wise formulation of the First Dual Distance Bound. We then establish conditions under which this upper bound is attained. We apply our results to several important families of linear codes, including MDS codes, Reed-Muller codes, constacyclic codes, and extended Golay codes, and obtain exact values of the maximum aggregate service rates for the corresponding subsets of data objects.

0.25

The Generalized Random Access Problem for Linear Codes

cs.IT math.CO ·2026-08-20 ·Anina Gruica, Antonio Petrillo, Ferdinando Zullo
hot direction similarity 0.64
Abstract

Random access is a central requirement in DNA-based storage systems: one would like to recover selected information symbols without sequencing the whole encoded object. A recent combinatorial model associates to a generator matrix $G\in F_q^{k\times n}$ the random variable $τ_i(G)$, measuring the number of sampled columns needed to recover the information vector $e_i$. We study the cardinality-based extremal and finite-geometric aspects of simultaneous multi-symbol recovery. For a nonempty set $I\subseteq[k]$, let $τ_I(G)$ denote the number of random column samples needed until all vectors $e_i$, $i\in I$, lie in the span of the observed columns. This variable interpolates between the singleton random access problem and the full-recovery problem underlying coverage depth. For each $m$, we introduce uniform worst-case and average parameters over all requested sets $I$ with $|I|=m$. Using the known subset-counting formula for $E[τ_I(G)]$, we establish general upper and lower bounds for these parameters. In particular, the lower bounds are expressed through order statistics of the singleton recovery variables and specialize to the known singleton bounds when $m=1$. For systematic MDS encoders, we record an equivalent form of the known multi-symbol expectation formula and derive monotonicity and asymptotic consequences. For simplex encoders in arbitrary dimension, we obtain closed formulae in terms of Gaussian binomial coefficients; the full-recovery endpoint agrees with the known coverage-depth formula for simplex codes. Finally, in dimension three we study balanced quasi-arcs and compare their values with the simplex and MDS benchmarks.

0.49

Replica Thresholds for Stripeless Erasure Coding Based on Symmetric Block Designs

cs.IT ·2026-09-24 ·Guiwen Luo, Xiao Li, Yaqiang Zhang, Ke Wang
similarity 0.61
Abstract

This paper investigates a fundamental question in stripeless erasure coding based on symmetric balanced incomplete block designs (SBIBDs): how many replicas per object are precisely required to guarantee recovery from any set of at most $p$ node failures? We refine the known sufficient recovery guarantee for the generalized SBIBD $(v,k,λ)$ construction. One replica is necessary and sufficient for $p=1$, and $q=λ(p-1)+2$ replicas ($q\le k$) guarantee recovery for $p\ge2$. Recovery takes one round for $p=2$ and at most two rounds in general. To study the tightness of this count, we define the universal replica threshold $q^\ast(A,p)$ for a fixed zero-diagonal SBIBD representative~$A$. We determine $q^\ast(A,p)$ for $p=1$ and $p=2$. For $p\ge3$, we identify pairwise separated sets and private target permutations as the structures determining whether the sufficient count is tight or can be further reduced. These conditions give exact thresholds for all but the case where $λ>1$ and $A$ contains no pairwise separated set of size~$p$. We improve the bounds for this remaining case and leave its exact threshold open. Finally, we give sufficient conditions for pairwise separated sets and show how affinity relabeling can realize private target permutations.

0.29

Multi-View Block Distance Distributions and Linear Programming Bounds for Locally Recoverable Codes with Availability

cs.IT math.CO ·2026-09-30 ·Ming-Hsuan Kang, Maosheng Xiong, Yu Hsuan Hsieh, Po-Wei Lai
similarity 0.61
Abstract · 16 pages, 2 tables

We develop a multi-view linear-programming framework for locally recoverable codes with arbitrary fixed availability $a$. For any retained order $1 \le s \le a$, the selected helper sets, the recovered coordinate, and their complement form an $(s+2)$-part partition. Recording the Hamming distance on all blocks preserves both compatibility among the selected repair alternatives and their coupling with the remaining coordinates. The resulting joint distribution satisfies centered counting identities, product-Krawtchouk positivity, and collision inequalities from the local-distance condition; for fixed $s$, these constraints give a polynomial-size relaxation for arbitrary, possibly nonlinear, codes over any finite field. Retaining one view recovers the three-block model of our companion paper. We develop the first genuinely multi-view case, $s=2$, in detail and specialize the exact computations to availability $a=2$. The resulting four-block LP projects to both the one-view three-block model and a globally conditioned two-view relaxation, making explicit the information lost by each coarsening. Exact rational primal-dual certificates together with checked constructions prove $M_{\max}(2,8,4,2,2,2)=8$, $M_{\max}(3,7,3,2,2,2)=27$, and $M_{\max}(4,7,3,2,2,2)=64$; in all three cases the four-block bound is strictly stronger than both coarsenings.

0.19

From Linear Exact Repair to Mixed-Alphabet Codes: The Bandwidth-Subpacketization Tradeoff of MDS Array Codes

cs.IT ·2026-10-21 ·Zihao Zhang, Guodong Li, Sihuang Hu
theory similarity 0.61
Abstract

MDS array codes achieve optimal storage efficiency in distributed storage systems, but their repair bandwidth depends critically on the sub-packetization level. While the theoretically optimal repair bandwidth (i.e., cut-set bound) of a high-rate exact-repair MDS array code is attainable with sufficiently large sub-packetization, the fundamental limits for fixed sub-packetization remain poorly understood. We study this problem for centralized linear exact repair of $h$ failures from $d$ helper nodes over a fixed finite field. We show that the rank profile of any linear repair scheme is constrained by two auxiliary mixed-alphabet codes. The first code is formed from the kernels of the helper projections and exists for all repair degrees; the second is formed from their row spaces and applies in the full-helper regime when $d\ge r$. These codes have complementary alphabet profiles, and their size and minimum-distance requirements are forced solely by the MDS property and repair correctness. This gives a unified route from classical coding-theoretic upper bounds to repair-bandwidth lower bounds. As a consequence, we obtain several explicit lower bounds via Singleton, Hamming, Plotkin, and Griesmer arguments, including known bounds as corollaries. We further formulate a Delsarte-type support-enumerator LP for mixed-alphabet codes and give an exact type-compressed implementation. For fixed sub-packetization \(\ell\), this yields a polynomial-time procedure for evaluating the resulting finite-parameter lower bound.

0.22

A General Plotkin-type Bound on Function-Correcting Codes with Wyner-Graham Distance

cs.IT cs.DM ·2026-08-30 ·Kanchana Lokshmii Jagatti, K. Hareesh, N. T. Rashid Ummer, B. Sundar Rajan
similarity 0.60
Abstract · 22 pages; Submitted to a journal

Function correcting codes (FCCs) are designed to protect a specified function evaluation of messages at a higher level than the level of protection for messages, against errors while reducing the redundancy required for reliable communication. FCCs have thus far been studied for channels matched to various distances, including the Hamming and Lee distances. Every function partitions the message space into preimage sets corresponding to its distinct function values. Existing Plotkin-type bounds on the optimal redundancy of FCCs under the studied distances, applicable to arbitrary functions on the message space, depend on the pairwise distances among all the message vectors. This makes these bounds difficult to compute. We derive a general Plotkin-type bound on the optimal redundancy of FCCs under Wyner Graham distances, which include the Hamming and Lee distances as special cases. Our bound depends only on the cardinalities of the preimage sets and the sum of pairwise distances only among vectors within each preimage set. This approach significantly reduces the computations required to evaluate the existing Plotkin-type bounds and yields simplified bounds that are easier to compute for specific functions. We obtain simplified Plotkin-type bound for linear functions under the Wyner-Graham distance. Furthermore, the existing simplified bounds for linear functions under the Hamming and Lee distances are recovered as special cases of the proposed bound. We also obtain simplified bounds for several important classes of functions, including the Hamming weight function, the Hamming weight distribution function, the monomial functions under the Hamming distance, and the modular sum function, the Lee weight function, and the Lee weight distribution function under the Lee distance.

0.11

Amortized Relaxed Locally Decodable Codes

cs.IT cs.DM ·2026-09-14 ·Jeremiah Blocki, Justin Zhang
similarity 0.59
Abstract

Locally decodable codes (LDCs) enable recovery of any message symbol by probing only a small number of positions in a possibly corrupted codeword. The central parameters of an LDC are its rate, locality, and error tolerance. Ideally, one would like all three parameters to be constant. However, classical lower bounds show that such codes cannot exist. A recent line of work introduced amortized locally decodable codes (aLDCs), in which the decoder is tasked with recovering an entire block of consecutive message symbols rather than a single symbol. While prior work obtained ideal aLDCs with constant rate, constant error tolerance, and constant amortized locality, those constructions relied on either shared randomness hidden from the channel or computational assumptions restricting the channel. Another well-studied relaxation is the notion of a relaxed locally decodable code (RLDC), in which the decoder may output a special failure symbol $\bot$ rather than risk decoding incorrectly. In this work, we introduce the notion of an amortized relaxed locally decodable code (aRLDC), combining amortized decoding with the relaxed decoding paradigm. Unlike prior ideal aLDC constructions, our model is fully information-theoretic and makes no assumptions about shared randomness or computational limitations of the adversarial channel. We construct the first aRLDC with constant rate, constant error tolerance, and constant amortized locality. Moreover, for any block of length $Ω(\mathrm{polylog}(k))$, our decoder achieves amortized locality $1+δ^{1 - o(1)}$, where $δ$ is the error tolerance parameter. Thus, asymptotically, recovering a long block requires essentially less than two codeword probe per message symbol recovered. By contrast, without amortization no RLDC can simultaneously achieve constant rate, constant error tolerance, and constant locality.

0.17

Optimal-Access Cooperative MSR Codes: Parity-Check Matrix Construction And a Unified Transformation

cs.IT ·2026-09-06 ·Yaqian Zhang, Jingke Xu, Ya-Feng Liu
theory similarity 0.59
Abstract

Cooperative MSR codes are a kind of storage codes which enable optimal-bandwidth repair of any $h\geq2$ node erasures in a cooperative way, while retaining the minimum storage as an $[n,k]$ MDS code. Each code coordinate (node) is assumed to store an array of $\ell$ symbols, where $\ell$ is termed as sub-packetization. To address the disk IO (input/output) capability, a cooperative MSR code is said to have optimal-access property, if during node repair, the amount of data accessed at each helper node meets a lower bound on this quantity. In this paper, we focus on reducing the sub-packetization level of optimal-access cooperative MSR codes. We propose new constructions of optimal-access cooperative MSR codes through two methods. At first, we propose a direct explicit construction by designing its parity-check matrix. Such parity-check matrix is built by repeatedly employing two crucial parity-check matrices as building blocks. Secondly, we propose a generic transformation framework. Starting from an arbitrary $[n+d-k,d]$ MDS scalar code, one can derive a final cooperative MSR code by systematically applying two basic transformations. Both approaches yield $(n,k,\ell=δ^m)$ optimal-access cooperative MSR codes with $δ=d-k+h$ and $m=\binom{n}{h}-\lfloor\frac{n}δ\rfloor(\binomδ{h}-1)$. Compared with the state of the art (with $\ell=δ^{\binom{n}{h}}$), the derived codes can reduce the sub-packetization $\ell$ by a fraction of $1/δ^{\lfloor\frac{n}δ\rfloor(\binomδ{h}-1)}$, where $δ=d-k+h$. Moreover, we also show that some previous code structures of optimal-access cooperative MSR codes and optimal-access MSR codes with $h=1$ are included as special cases of our transformation construction. At last, we note that all of the constructions are built over a finite field of linear size $\geq n+d-k$.

0.30