PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Conversion Bandwidth for MDS Convertible Codes in the Split Regime with $r^F<k^F<r^I$

Lewen Wang, Sihuang Hu

arXiv:2610.08349v1cs.ITmath.IT

TL;DR

The tight split-regime bandwidth bound for stable MDS convertible codes remained unresolved when rF < kF < rI. This paper derives new rank inequalities and constructs codes that attain a three-case bound, establishing the optimum in that range within the stable linear conversion model.

  • Problem

    Prior split-regime bandwidth bounds were tight in other parameter ranges, but tightness remained unresolved for rF < kF < rI.

    Source: §1 · pp. 1–2

  • Method

    The paper derives rank inequalities from coordinate projections for stable linear MDS convertible codes and solves the resulting linear program.

    Source: §1 · p. 2, §2 · p. 3, §5 · p. 19

  • Results

    Three explicit constructions attain the three-case lower bound, making it tight throughout rF < kF < rI in the stable linear conversion model.

    Source: §5 · p. 19

  • Takeaways & Limitations

    Because stable conversion fixes write bandwidth, the tight read-bandwidth bound determines minimum total conversion bandwidth in this regime.

    Source: §5 · p. 19

    The results are within the stable linear conversion model; future work includes reducing construction field sizes to linear in code length and finding the exact optimum at prescribed subpacketization without enlarging ℓ.

    Source: §2 · p. 3, §5 · p. 19

Abstract

from arXiv · show

Erasure codes are widely used in distributed storage systems to provide fault tolerance. An $[n,k]$ erasure code encodes $k$ data symbols into $n$ coded symbols and distributes them across $n$ storage nodes. Once the code parameters are fixed, the achievable fault tolerance is also fixed. However, the failure rates of storage nodes may vary over time, and dynamically adapting the code parameters to these variations can substantially reduce storage overhead. Motivated by this observation, Maturana and Rashmi introduced convertible codes, which allow an $[n^I,k^I]$ initial code with redundancy $r^I=n^I-k^I$ to be transformed into an $[n^F,k^F]$ final code with redundancy $r^F=n^F-k^F$, while preserving the required code properties. Convertible codes whose initial and final codes are both MDS codes are called MDS convertible codes. They are of particular interest because MDS codes provide the maximum erasure tolerance for a given amount of storage overhead. Several works have established lower bounds and constructions for the bandwidth cost of MDS convertible codes in the split regime. However, the tight bound in the parameter range $r^F<k^F<r^I$ remains unknown. In this work, we establish a family of new rank inequalities for stable MDS convertible codes with linear conversion procedures and derive an improved lower bound on the bandwidth cost consisting of three cases for this remaining range. We prove that the bound is tight by presenting three explicit constructions, one for each case.

1 Introduction

Convertible codes let storage systems adapt code parameters as device reliability changes, while MDS codes retain optimal erasure tolerance. This paper resolves the open bandwidth-bound regime rF < kF < rI for stable linear MDS convertible codes, with matching constructions.

1 Introduction

  • Convertible codes transform an initial code into a final code with different parameters while preserving desired properties, avoiding full decode-and-re-encode costs.MDS convertible codes have MDS initial and final codes; MDS codes provide optimal erasure tolerance for their storage overhead.Source: §1 · pp. 1–2
  • The split regime converts one initial codeword into several final codewords, and split and merge conversions are building blocks for broader conversions.Code parameters can be adapted as device failure rates change, potentially reducing storage overhead while maintaining prescribed reliability.Source: §1 · pp. 1–2
  • Earlier split-regime bandwidth bounds were tight for rF ≥ kF or rI ≤ kF, leaving rF < kF < rI unresolved.Prior stronger bounds for the remaining range relied on an additional conjecture.Source: §1 · p. 2
  • The new rank inequalities strengthen the read-bandwidth lower bound in the remaining regime rF < kF < rI, yielding a three-case bound.They recover prior constraints when rF < kF and rI ≤ kF; the additional inequalities strengthen the bound in the remaining range.Source: §1 · p. 2
  • Three explicit constructions attain the corresponding lower bounds, one for each case.Cases I and II use anchor rows and an invertible transformation to obtain a Cauchy submatrix; Case III uses a two-layer auxiliary MDS array code.Source: §1 · pp. 2–3
  • The bounds are tight throughout rF < kF < rI in the stable linear conversion model when integrality conditions are met.The required subpacketization can be chosen polynomial in nI; stable conversion has fixed write bandwidth, so the result also determines minimum total bandwidth.Source: §1 · p. 3

2 Preliminaries

The preliminaries define the code, conversion, and bandwidth conventions used in the paper. They also give a systematic representation and characterize when a linear stable conversion can use specified subsymbols.

2 Preliminaries

  • An array code is a kℓ-dimensional subspace with n symbols of ℓ subsymbols, and it is MDS when any k symbols recover the codeword.A generator matrix encodes a message by multiplication; each scalar within a symbol is a subsymbol.Source: §2 · p. 3
  • A split-regime MDS convertible code pairs initial and final MDS array codes with a conversion procedure mapping λ initial-code messages to λ final codewords.The parameterization has kI = λkF.Source: §2 · p. 3
  • The paper considers linear conversions that read subsymbols directly, with each new-symbol subsymbol an Fq-linear combination of those read.For each initial symbol, Di records the read subsymbol coordinates and βi = |Di|; total read bandwidth is the sum of βi.Source: §2 · pp. 3–5
  • Stable conversion maximizes unchanged symbols; in the split setting it has exactly kI unchanged symbols, making write bandwidth λrFℓ and total-bandwidth minimization equivalent to minimizing read bandwidth.Stability is defined relative to MDS convertible codes with the same parameters.Source: §2 · p. 4
  • After suitable node permutations and invertible message-coordinate changes, the unchanged initial symbols can be placed first in λ groups matching the final codewords.The resulting initial and final generator-matrix blocks are block superregular, meaning every square block submatrix is nonsingular.Source: §2 · pp. 4–5
  • The linear-conversion characterization gives a necessary-and-sufficient condition for specified read sets and states that achievable read bandwidth is x + rank(eB).The characterization's arguments do not require the final-code matrices Ct to coincide.Source: §2 · p. 5
  • Linnik’s theorem is introduced for use in the Case III construction in Section 4.3.3.The stated lemma concerns a bound on the least prime satisfying a congruence condition.Source: §2 · p. 5

3 A Family of Rank Inequalities and Improved Lower Bounds

For stable MDS split conversions with linear procedures, the section derives rank inequalities and uses them to lower-bound read bandwidth. In rF<kF<rI, the inequalities yield a stronger bound through additional constraints.

3.1 A Family of Rank Inequalities

  • Coordinate projections of the initial and final code column spaces yield additional rank constraints used to bound read bandwidth.Source: §3.1 · p. 6
  • When rI≤kF and rF<kF, the additional inequalities are redundant, recovering the previous lower bound matched by a construction.Source: §3.1 · p. 8

3.2 Improved Lower Bounds for rF < kF < rI

  • For rF<kF<rI, constraints with s≥2 add to the s=0,1 constraints and can strengthen the read-bandwidth lower bound.Source: §3.1 · p. 8
  • In the first case, the LP optimum is λrFℓ when λkF≤rI.Source: §3.2 · p. 8

4 Explicit Constructions Attaining the Lower Bounds

The constructions attain the lower bounds from Theorem 1 while preserving the MDS property and all initial systematic symbols.

4 Explicit Constructions Attaining the Lower Bounds

  • All λ final codewords use the same systematic generator matrix, with initial and final parity blocks B and C.Source: §4 · p. 11
  • Block-superregular B and C ensure that both the initial and final codes are MDS.Source: §4 · p. 11
  • The linear conversion preserves all kI systematic symbols and attains the corresponding read-bandwidth lower bound, with ℓ chosen to make per-node read amounts integral.Source: §4 · p. 11

4.1 Case I: rI ≥kI

Case I achieves the optimal read bandwidth using downloads only from retired parity nodes. The construction pairs an MDS final code with an MDS initial code and a linear conversion preserving all initial systematic symbols.

4.1 Case I: rI ≥kI

  • R = λrFℓ is the optimal read bandwidth, attained by downloading subsymbols only from retired parity nodes.No systematic subsymbols are read.Source: §4.1 · p. 11

4.1.1 Construction of the final code CF

  • The final code is formed by designating anchor rows in its parity transform; its generator matrix generates an MDS array code.The construction uses a block-diagonal replication of the final parity transform across the λ final groups.Source: §4.1.1 · p. 11

4.1.2 Construction of the initial code CI

  • An invertible transformation L satisfying AL = E gives Z = ML and D = FL, and the resulting initial code is MDS.The initial parity blocks combine E, Z, and Q in a block-triangular structure.Source: §4.1.2 · p. 12

4.1.3 Conversion and field size

  • Reading no systematic subsymbols and σ subsymbols from each retired parity node permits linear conversion preserving all kI systematic symbols at the Case I lower bound.The read bandwidth is R = rIσ = λrFℓ.Source: §4.1.3 · p. 12

4.2 Case II: kF < rI < kI and Γ ≥1

In Case II, the optimal read bandwidth is attained by reading subsymbols from unchanged systematic nodes and retired parity nodes. The construction uses anchor-row transformations to produce MDS initial and final codes whose column spaces permit linear conversion.

4.2 Case II: kF < rI < kI and Γ ≥1

  • R = (kI)^2rFℓ/∆ is the optimal read bandwidth and attains the Case II lower bound.Here ∆ = rI(kF − rF) + kIrF.Source: §4.2 · p. 12, §4.2.3 · p. 15

4.2.1 Construction of the final code CF

  • The final code orders each systematic block into anchor, read, and remaining unread coordinates, and its generator matrix generates an MDS array code.The construction selects w anchor rows from each block and retains block superregularity under the row permutation.Source: §4.2.1 · pp. 13–14

4.2.2 Construction of the initial code CI

  • An invertible L maps A to Ean and gives Z = ML and D = FL; the resulting block-triangular initial parity matrix is block superregular, so the initial code is MDS.The construction uses Cauchy matrices E and Q.Source: §4.2.2 · pp. 14–15

4.2.3 Conversion and field size

  • Reading β coordinates from each unchanged systematic node and σ from each retired parity node permits linear conversion preserving all kI systematic symbols at the Case II lower bound.The read bandwidth is R = kIβ + rIσ = (kI)^2rFℓ/∆.Source: §4.2.3 · p. 15

4.3 Case III: kF < rI < kI and Γ < 1

Case III attains its lower bound by reading from unchanged systematic nodes and retired parity nodes. Its constructions use a Cauchy-based final code and a two-layer auxiliary MDS array code to establish the column-space inclusion needed for conversion.

4.3 Case III: kF < rI < kI and Γ < 1

  • Reading β subsymbols from each unchanged systematic node and σ from each retired parity node attains the Case III lower bound.The construction establishes that these downloads permit linear conversion preserving all kI systematic symbols.Source: §4.3 · p. 15, §4.3.3 · pp. 18–19

4.3.1 Construction of the final code CF

  • The final code uses a Cauchy matrix construction whose block superregular parity matrix generates an MDS array code.The construction distinguishes anchor rows from the remaining rows and uses a second Cauchy matrix QF.Source: §4.3.1 · pp. 15–16

4.3.2 Construction of the initial code CI

  • The auxiliary code E combines weighted and ordinary polynomial evaluations with a Reed–Solomon second layer, and any rI auxiliary nodes recover the message, making E MDS.Its first w rows per block row form Ean, with col(Fan) ⊆ col(Ean).Source: §4.3.2 · pp. 17–18

4.3.3 Conversion and field size

  • The initial code is MDS, and the constructed conversion satisfies col(eC) ⊆ col(eB), permitting linear conversion with read bandwidth at the Case III lower bound.The construction establishes EanJ = Fan and ZJ = Flo before showing the column-space relation.Source: §4.3.2 · p. 18, §4.3.3 · p. 19

5 Conclusion

For stable MDS convertible codes with linear conversion in the split regime rF < kF < rI, the paper derives an improved three-case lower bound and gives constructions attaining it. This makes the bound tight throughout the regime and determines minimum total conversion bandwidth.

5 Conclusion

  • Coordinate-projection rank inequalities strengthen the lower bound in rF < kF < rI and yield three cases by solving a linear program.They recover previous lower bounds when rF < kF and rI ≤ kF.Source: §5 · p. 19
  • Cases I and II use anchor rows mapped to a Cauchy submatrix, while Case III uses a two-layer auxiliary MDS array code.Case III combines structured polynomial evaluations in its first layer with a Reed–Solomon code in its second.Source: §5 · p. 19
  • The three constructions attain the lower bounds throughout rF < kF < rI, determining minimum total conversion bandwidth for stable conversion.The required integrality conditions can be satisfied by choosing subpacketization ℓ appropriately, with ℓ polynomial in nI.Source: §5 · p. 19
  • Future work includes reducing all three constructions’ field sizes to linear in code length and finding exact optima at fixed ℓ when LP-optimal read amounts are nonintegral.The latter remains open without enlarging ℓ.Source: §5 · p. 19
Loading 2610.08349v1…