Tight Lower Bounds and Optimal Constructions of Locally Repairable Convertible Codes in the Split Regime

Technical Summary: Tight Lower Bounds and Optimal Constructions of Locally Repairable Convertible Codes in the Split Regime

Problem Statement
Modern distributed storage systems rely on erasure codes, particularly Locally Repairable Codes (LRCs), to balance storage efficiency, fault tolerance, and repair bandwidth. However, as system parameters (such as failure rates or scale) evolve over time, the coding parameters often require adjustment. This necessitates code conversion, where data encoded under an initial code is transformed into data encoded under a final code. While prior work has established bounds for converting Maximum Distance Separable (MDS) codes and LRCs in the merge regime (combining codewords), the global split regime (splitting one codeword into multiple) for LRCs remains less understood. Specifically, no read-bandwidth lower bounds were known for stable conversions of optimal-distance LRCs in the split regime, and it was unclear whether existing constructions achieved optimal efficiency. This paper addresses the conversion of stable optimal-distance $(k, g, r, \ell)$-LRCs in the global split regime, focusing on the parameter range where the number of global parity nodes in both initial and final codes does not exceed the local dimension ($g_I, g_F \le r$).

Methodology
The authors employ a two-pronged approach: information-theoretic converse analysis and constructive achievability.

1. Information-Theoretic Lower Bounds:

   • The paper extends information-theoretic approaches used in MDS convertible codes to the LRC setting.
   • It establishes structural properties of stable conversions in the split regime: all initial global parity nodes must be retired, all final global parity nodes must be newly generated, and unchanged local parity nodes must remain associated with the same local group.
   • Using entropy inequalities and the properties of optimal-distance LRCs (specifically, that global parity nodes depend on all information nodes and that local groups behave like MDS codes when conditioned on other groups), the authors derive two fundamental constraints on the data downloaded during conversion.
   • These constraints lead to piecewise lower bounds on the read bandwidth, dependent on the relative sizes of the initial global parity count ($g_I$) and the final global parity count ($g_F$).

2. Optimal Constructions:

   • To prove the tightness of the lower bounds, the authors construct stable optimal-distance Locally Repairable Convertible Codes (LRCCs) using MDS array codes with prescribed repair properties.
   • The construction utilizes the piggybacking framework. The authors design specific MDS array codes where parity nodes can be optimally repaired by downloading specific subsets of subsymbols from helper nodes.
   • The construction is divided into three cases based on the relationship between $g_I$ and $g_F$:
     • Case $g_F = g_I$: Uses a single layer of local-parity piggybacks.
     • Case $g_F > g_I$: Employs a combination of local-parity piggybacks and "head-global" piggybacks to handle the increase in global parity nodes.
     • Case $g_F < g_I$: Utilizes a more complex structure involving logical cyclic ordering of prefix blocks and specific alignment of tail piggybacks to handle the reduction in global parity nodes.
   • In all cases, the constructions ensure that information nodes and local parity nodes are preserved (maximizing stability), and the read bandwidth exactly matches the derived lower bounds over sufficiently large finite fields.

Key Contributions and Results

• First Lower Bounds: This work provides the first read-bandwidth lower bounds for stable optimal-distance LRCCs in the global split regime. These bounds are derived without imposing linearity assumptions on the codes or the conversion procedure.
• Optimality Characterization: The paper characterizes the fundamental optimal read-bandwidth cost for the entire parameter range $g_I, g_F \le r$. The derived lower bounds are shown to be tight via explicit constructions.
• Sub-optimality of Prior Work: By comparing the derived optimal bounds with the global split constructions proposed by Maturana and Rashmi [13], the authors demonstrate that the prior constructions are not bandwidth-optimal in general for this parameter regime. The gap is shown to be strict unless specific trivial conditions (e.g., $u=1$ and $g_F=r$) are met.
• Case-Specific Solutions: The paper provides distinct, optimal constructions for the three sub-cases ($g_F = g_I$, $g_F > g_I$, and $g_F < g_I$), detailing the specific piggybacking strategies required to achieve optimality in each scenario.

Significance
The paper claims to resolve an open problem raised in prior literature regarding the bandwidth optimality of LRC conversions in the global split regime. By establishing tight lower bounds and providing matching constructions, the work definitively characterizes the cost of adapting optimal-distance LRCs in the split regime. The results indicate that while dynamic code adaptation is feasible, achieving it with minimal read bandwidth requires specific code structures (piggybacked MDS array codes) that differ from previous general approaches. The findings suggest that existing conversion schemes may incur unnecessary read overhead, and the proposed constructions offer a path to optimal efficiency for systems operating within the $g_I, g_F \le r$ constraints.