PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Priyanka Choudhary, Maheshanand Bhaintwal

arXiv:2610.01900v1cs.ITmath.COmath.IT

TL;DR

In distributed storage, service capacity depends on which disjoint recovery sets can serve requests, and understanding that structure can become difficult as it grows. This paper characterizes how Plotkin-type construction changes recovery sets and uses the resulting hypergraphs to bound service rates, including recursive analysis of first-order binary Reed–Muller codes.

  • Problem

    The paper addresses how a standard code construction transforms a parent code’s recovery structure and SRR, a perspective described as largely absent from prior work.

    Source: §I · pp. 1–2

  • Method

    The authors characterize minimal recovery sets in a Plotkin-type code from those of its parent and use recovery hypergraphs and fractional matchings to analyze service rates.

    Source: §I · p. 2, C. Service Rate Region and Fractional… · p. 4, §III · p. 9

  • Results

    The results provide service-rate bounds for Plotkin-type codes and iterated constructions, and a recursive route to analyzing R(1, m) from R(1, 2).

    Source: §I · p. 2, §IV · p. 12, §V · p. 14

  • Takeaways & Limitations

    For the Plotkin construction, any gain in service flexibility reflects increased flexibility rather than improved storage efficiency.

    Source: §I · p. 2

Abstract

from arXiv · show

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.

I. INTRODUCTION

The service rate region (SRR) depends on both code parameters and the combinatorial structure of recovery sets. This work studies how Plotkin-type construction transforms that structure and the resulting service rates.

I. INTRODUCTION

  • The SRR is the set of request-rate vectors a storage system can support simultaneously, and achievable rates depend on the code’s recovery-set structure.Requests may be served from any recovery set of the requested data object.Source: §I · p. 1
  • Prior work studied SRRs for several code families, but analysis becomes difficult when recovery graphs or hypergraphs cannot be explicitly enumerated.The literature also examined Reed–Muller recovery structures and how code constructions transform recovery sets and service rates.Source: §I · p. 1
  • The paper identifies a gap in understanding how a standard construction transforms a known code’s SRR; Plotkin construction doubles servers while adding one information object.Any gain from this construction therefore reflects increased flexibility rather than improved storage efficiency.Source: §I · p. 2
  • The authors characterize minimal recovery sets in the Plotkin-type code from those in the parent code, including additional recovery sets introduced by the construction.They also establish a correspondence between recovery sets for the same information object in the two codes.Source: §I · p. 2
  • The paper derives service-rate bounds for Plotkin-type and iterated codes, and recursively analyzes first-order binary Reed–Muller codes from R(1, 2).The paper’s organization assigns recovery-set characterization to Section III and service-rate bounds and Reed–Muller applications to Section IV.Source: §I · p. 2

II. PRELIMINARIES

The preliminaries establish the notation and concepts used to analyze coded storage systems and the Plotkin-type construction.

II. PRELIMINARIES

  • The section recalls basic notions of linear codes used throughout the paper.It then introduces recovery sets and their hypergraph representation.Source: §II · p. 2
  • The preliminaries define the service rate region for a coded distributed storage system.Source: §II · p. 2
  • The section describes the Plotkin-type construction examined in the paper and its corresponding generator matrix.Source: §II · p. 2

A. Linear Codes

This section sets out notation and core definitions for linear codes, their generator matrices, and their duals.

A. Linear Codes

  • A q-ary linear [n, k, d] code is a k-dimensional subspace of Fq^n with minimum Hamming distance d.Source: A. Linear Codes · p. 2
  • A rank-k generator matrix has rows forming a basis of the code, and an information vector u encodes to the codeword u · G.A column is systematic for i when it is a nonzero scalar multiple of the standard basis vector ei.Source: A. Linear Codes · p. 2
  • The dual code C⊥ has parameters [n, n−k, d⊥], and a generator matrix of C⊥ is a parity-check matrix H satisfying G · H⊤ = 0.Source: A. Linear Codes · pp. 2–3

B. Recovery Sets and Hypergraph Representation

The section defines recovery sets for information symbols and represents their minimal forms as labeled hyperedges, enabling combinatorial analysis of recovery capacity.

B. Recovery Sets and Hypergraph Representation

  • A set of server coordinates recovers information symbol xi when the corresponding generator-matrix columns span ei.A recovery set is minimal when none of its proper subsets also recovers the symbol.Source: B. Recovery Sets and Hypergraph… · p. 3
  • For a systematic generator matrix, a non-singleton recovery set excluding i corresponds to a dual-codeword support containing i and contained in the set together with i.Dual supports are supports of codewords in C⊥; inclusion-minimal supports represent minimal dependencies among generator-matrix columns.Source: B. Recovery Sets and Hypergraph… · p. 3
  • The recovery hypergraph uses storage nodes as vertices and minimal recovery sets as hyperedges labeled by their information symbols.A partial recovery hypergraph retains hyperedges for the selected information symbols.Source: B. Recovery Sets and Hypergraph… · p. 3
  • A matching is a collection of pairwise vertex-disjoint hyperedges, while a vertex cover intersects every hyperedge.Relaxing their integrality constraints yields fractional matching and fractional vertex-cover notions.Source: B. Recovery Sets and Hypergraph… · p. 3

C. Service Rate Region and Fractional Matchings

The service rate region describes request-rate vectors supportable under server-capacity constraints. Recovery hypergraphs connect those constraints to fractional matchings, which characterize feasible allocations and service rates.

C. Service Rate Region and Fractional Matchings

  • With unit-capacity servers, a request-rate vector is feasible when demand is allocated across recovery sets without exceeding any server’s capacity.It suffices to consider inclusion-minimal recovery sets when determining the SRR.Source: C. Service Rate Region and Fractional… · p. 4
  • The recovery hypergraph represents servers as vertices and recovery sets as hyperedges, turning feasible service allocations into fractional matchings.The SRR is the image of the fractional-matching polytope under the mapping to request-rate vectors.Source: C. Service Rate Region and Fractional… · p. 4
  • The maximum achievable service rate is characterized by the hypergraph’s fractional matching number, and the matching–vertex-cover inequality also applies to partial recovery hypergraphs.The relation in equation (3) extends to partial recovery hypergraphs Γ_G(I).Source: C. Service Rate Region and Fractional… · p. 4

D. Codes and Their Plotkin-Type Construction

The Plotkin-type construction combines a binary linear code with a repetition-code component to form a longer code. Its parameters and associated matrices specify the resulting code and its dual constraints.

D. Codes and Their Plotkin-Type Construction

  • The Plotkin-type code is C_p = {(c,c): c∈C} ∪ {(c,1_n+c): c∈C}, formed from a binary linear code C of length n.The construction uses C and a length-n repetition code.Source: D. Codes and Their Plotkin-Type… · p. 5
  • C_p has parameters [2n, k+1, min{n,2d}], doubling code length and adding one information symbol.Here C is an [n,k,d] binary linear code.Source: D. Codes and Their Plotkin-Type… · p. 5
  • The construction specifies generator and parity-check matrices for C_p, with H′ an (n−1)×n parity-check matrix of the repetition code.The text identifies O as the (n−k)×n zero matrix.Source: D. Codes and Their Plotkin-Type… · p. 5

III. RECOVERY SET STRUCTURE AUGMENTATION AND SRR FOR INDUCTIVE CODES

This section characterizes how the Plotkin-type construction preserves and augments recovery sets for existing information symbols, using even-subset mappings and, for systematic codes, constructions involving triples and dual supports. An example based on an underlying [6, 3] code illustrates the augmentation for each information symbol.

Correspondence and new sets

  • Every recovery set for an existing symbol induces a recovery set in the original code; conversely, each nonempty even subset of an original recovery set yields a new recovery set.Theorem 1 also requires the second-half coordinates of a recovery set to have even cardinality; Theorem 2’s induced set is minimal.Source: §III · pp. 6–7

Recovery of the new symbol

  • For the newly added information symbol, the constructed code has n disjoint recovery sets, each consisting of a coordinate pair {j, j + n}.These pairs recover the new symbol because their two codeword symbols sum to it.Source: §III · pp. 6–7

Counts and disjointness

  • For an original recovery set of size r, Theorem 3 gives 2^(r-1) − 1 new recovery sets, while t disjoint even-sized original sets yield at least 2t disjoint constructed-code recovery sets.For each even-subset-induced set, membership counts differ across paired coordinates: 2^(r-2) − 1 sets contain j, and 2^(r-2) contain j + n.Source: §III · p. 7

Systematic-code triples

  • With a systematic generator matrix, each j ≠ i gives a triple {j, j + n, i + n} recovering xi; the stated lower bound is 3t + n − 1 new triples when t original triples contain j.The counts for the constructed triples are tj + 1 containing j and 2tj + 1 containing j + n.Source: §III · pp. 7–8

Dual-support constructions

  • For systematic G, with minimal-inclusion dual support D, i∉D, and no R∈Ri(G) with R⊊D, odd subsets yield 2^(|D|−1) distinct recovery sets in Ri(Gp), each containing i+n.For Theorem 6, when D is inclusion-minimal, i∈D, and ℓ∉D satisfies its stated no-R condition, each such ℓ yields 2^(|D|−2) recovery sets DE.Source: §III · pp. 8–9

Theorem 7: complete characterization

  • Theorem 7 characterizes all minimal recovery sets for existing symbols in the constructed code from the original recovery sets and sets obtained by Theorems 2, 4, 5, and 6.This gives a method for determining the constructed code’s recovery-set structure from that of the underlying code.Source: §III · p. 9

Example 1

  • The six coordinate pairs {1, 7}, {2, 8}, {3, 9}, {4, 10}, {5, 11}, and {6, 12} belong to R4(Gp).These recovery sets follow from Part (ii) of Theorem 2.Source: §III · p. 11
  • For x1, the example explicitly gives eight sets in K and five in L as additional recovery families.The K sets are obtained using Theorem 2, with the first two also following from Corollary 1; L is obtained using Theorem 4.Source: §III · p. 11
  • For x1, R1(Gp) = R1(G) ∪ K ∪ L ∪ M ∪ N, and the same method obtains the recovery sets for x2 and x3.The added families are generated using Theorems 2, 4, 5, and 6.Source: §III · p. 11

A. Parameters of the Iterated Plotkin Construction

Repeated Plotkin steps define the iterated code C_{p^m} and determine how its parameters scale. Theorem 8 also gives a lower bound on size-3 recovery sets under specified conditions on the parent code.

A. Parameters of the Iterated Plotkin Construction

IV. ALLOCATIONS FOR SERVICE RATES IN Cp AND Cpm

This section derives service-rate bounds for Plotkin-type codes from the recovery structures of their parent codes. It treats the added information object separately and extends the analysis to iterated constructions.

IV. ALLOCATIONS FOR SERVICE RATES IN Cp AND Cpm

  • For the added information object, the section constructs matching and cover arguments separately, using the second block as a vertex cover because every recovery set contains a node there.The construction assigns weight 1 to second-block nodes and 0 to first-block nodes.Source: §IV · p. 12
  • For any subset of parent information objects, doubling an optimal vertex cover gives a cover for the Plotkin code, while its matching number does not decrease.The lifted cover is Vp = V ∪ (V + n).Source: §IV · p. 12
  • Fractional vertex covers of parent recovery hypergraphs can be lifted to the Plotkin code, providing bounds for inherited information objects.The section uses these cover constructions in deriving service-rate bounds.Source: §IV · pp. 12–13
  • When the added object is included, a parent vertex cover can be complemented across the second block to cover Plotkin recovery sets, and the resulting bound is achievable.The section also states that analogous results extend inductively to iterated Plotkin-type codes.Source: §IV · p. 13
  • In the example, parent-code matching and fractional-cover numbers are 3, while the Plotkin code’s added object has maximal achievable rate 6.For the Plotkin code, the matching and fractional-cover numbers are also 6 for subsets of the inherited information objects.Source: §IV · p. 13
  • n2^m−1 is a tight upper bound on summed request rates for the iterated-code case that includes the added information object.The bound applies to the subset of information objects specified in Theorem 13.Source: §IV · p. 13

A. Application to first-order binary Reed-Muller codes

The section applies successive Plotkin-type constructions to first-order binary Reed–Muller codes. It starts from R(1,2), develops recovery-set and hypergraph bounds for higher dimensions, and uses these results to derive service-rate information for arbitrary m.

A. Application to first-order binary Reed-Muller codes

  • The codes follow the recursion R(1,m+1) = {(c,c): c∈R(1,m)} ∪ {(c,c+1): c∈R(1,m)}, enabling the construction to proceed from lower-order codes.The section uses the recovery structure of R(1,2) as its starting point for the iterative application.Source: A. Application to first-order binary… · p. 14
  • R(1,2) has recovery sets R1 = {(1), (2, 3, 4)}, R2 = {(1, 2), (3, 4)}, and R3 = {(1, 3), (2, 4)}.These sets are given for the three information symbols in the code.Source: A. Application to first-order binary… · p. 14
  • For m≥3, the recovery-hypergraph analysis gives ν(Γ_i) ≥ 2^{m−1} and τf(Γ_i) ≤ 2^{m−1} for i∈[2,m].The section applies these matching and fractional-cover bounds in the iterative Reed–Muller construction.Source: A. Application to first-order binary… · p. 14
  • A recovery set of cardinality 3 for x1 in R(1,2) underlies a rate assignment that combines fractional requests on recovery sets with unit systematic-node service.The passage describes assigning requests of 1/(2^{m−1}−1) to each recovery set.Source: A. Application to first-order binary… · p. 14

V. CONCLUSION

The conclusion connects Plotkin-type recovery structures to service rates and identifies the scope of the derived results. It also names extensions left for future work.

V. CONCLUSION

  • The paper studies how standard code-construction operators affect service-rate regions when the parent code’s region is known.For the Plotkin-type construction, it establishes a correspondence between the parent and constructed codes’ recovery structures and achievable service rates.Source: §V · p. 14
  • The results provide service-rate bounds for iterated Plotkin constructions and derive service rates for binary first-order Reed–Muller codes for any m from a generator matrix of R(1,2).Source: §V · p. 14
  • Future work includes general (u | u + v) constructions with an arbitrary second code, q-ary codes, and other code constructions.Source: §V · p. 14
Loading 2610.01900v1…