1 Introduction↩︎

Distributed storage systems provide reliability by encoding data across multiple storage nodes using erasure codes. Two important and practically motivated aspects of such systems have been extensively studied: efficient node repair to handle individual node failures, and efficient code conversion to adapt to changing system requirements.

The problem of node repair is addressed by regenerating codes [1], which minimize the repair bandwidth by allowing each helper node to transmit a fraction of its stored data. Among these, Minimum Storage Regenerating (MSR) codes are of particular interest because they achieve the minimum possible storage overhead and optimal repair bandwidth. Explicit constructions of MSR codes have been proposed in [2]–[17].

Separately, as storage requirements evolve—due to data growth, node addition, or changes in fault-tolerance requirements—it becomes necessary to adapt the storage configuration without re-encoding from scratch. This problem is addressed by convertible codes [18], which enable the transformation from an initial code to a final code with different parameters while accessing only a subset of stored symbols. The performance of such schemes is measured by the access cost, i.e., the total number of symbols read during conversion, and the conversion bandwidth, i.e., the total amount of data downloaded across all nodes. Information-theoretic lower bounds for these metrics have been established for scalar MDS codes in [19] and [20]. The most well-studied setting is the merge regime [18], [19], [21]–[24], where \(m\) initial codewords are combined into a single final codeword of larger dimension, which is the setting we consider throughout this paper.

Although MSR codes achieve optimal repair bandwidth and convertible codes enable efficient transformation between different parameters, their integration remains challenging. Existing convertible-code constructions based on MDS codes do not preserve the repair structure, while MSR codes are designed for static settings and do not support efficient conversion. The main difficulty lies in a structural mismatch: code conversion reorganizes stripe layout and symbol placement, whereas MSR repair relies on a coordinate-wise structure enabling interference alignment. As a result, this structure is not preserved under conversion, making it difficult to achieve both efficient conversion and optimal repair simultaneously.

This motivates the study of convertible MSR codes, which support both efficient repair and efficient conversion. The main contributions are as follows.

First, we extend the scalar MDS conversion framework of [19] to array codes, providing a general foundation for our convertible MSR constructions.

Then, we construct explicit \((m,1)_q\) convertible MSR codes in the irregular setting that achieve optimal access cost, based on this framework and the Hadamard-design MSR construction [13]. The key idea is a subsymbol-level pre-alignment that preserves the periodic structure required for MSR repair under conversion.

Finally, we further consider the same-code setting, where all initial codewords are drawn from the same MSR code. By introducing a row-matching technique based on bijective row remapping, we obtain constructions simultaneously achieving optimal access cost and conversion bandwidth for \(r_F\leq\min\{k_I,r_I\}\) and \(r_F>k_I\). For the remaining regime \(r_I<r_F<k_I\), a new construction combining the conversion procedure with regenerating techniques achieves optimal conversion bandwidth. As a comparison, Table 1 presents parameters of previous results and ours. As shown in the table, existing constructions achieve at most two of the three desirable properties—optimal access cost, optimal conversion bandwidth, and optimal repair bandwidth—simultaneously. In contrast, the constructions proposed in this paper are the first to achieve all three properties at once, across different parameter regimes.

This article substantially extends our preliminary conference paper [25] in several important respects, including more general parameter regimes, a more general construction framework, and strengthened optimality analysis.

3pt

The remainder of the paper is organized as follows. Section 2 introduces notation and preliminaries. Section 3 presents the system model and formal definitions of convertible MSR codes. Section 4 presents the array MDS conversion framework. Section 5 presents the irregular and same-code constructions. Section 6 concludes the paper.

2 Preliminaries↩︎

An \((n,k;\alpha)_q\) array code \(\mathcal{C}\) is a subspace of \(\mathbb{F}_q^{n\alpha}\) with dimension \(k\alpha\). For a given codeword \(\mathbf{c}= (\mathbf{c}_0,\dots,\mathbf{c}_{n-1})\in\mathcal{C}\), denote by \(\mathbf{c}_i=(c_{0,i},\dots,c_{\alpha-1,i})\) for \(i\in[0,n-1]\) the \(i\)-th symbol of \(\mathbf{c}\). Moreover, each node stores one vector symbol of length \(\alpha\), and we call each component \(c_{w,i}\) in this vector a subsymbol for \(i\in[0,n-1]\) and \(w\in[0,\alpha-1]\).

We use generalized Reed-Solomon codes as a base code to design convertible codes. The definition is given below.

In particular, when \(\boldsymbol{\nu}=(1,\ldots,1)\), the resulting code is the classical Reed–Solomon (RS) code. The dual of an RS code is also a generalized Reed–Solomon code. Specifically, for an \([n,k]\) RS code with evaluation points \(\Lambda=\{\lambda_{0},\ldots,\lambda_{n-1}\}\subseteq \mathbb{F}_q\), the coefficients of its dual code are given by \[\label{eq:32coefficient} \nu_i = \prod_{\substack{j\in[0,n-1]\\ j\neq i}}(\lambda_i-\lambda_j)^{-1}, \qquad i\in[0,n-1].\tag{1}\]

Clearly, the coefficients \(\boldsymbol{\nu}\) are uniquely determined by the evaluation points.

We next recall the notion of puncturing.

Thus, for an \([n,k]\) GRS codeword \(\mathbf{c}=(c_0,\cdots,c_{n-1})=(\nu_{0}f(\lambda_{0}),\cdots,\nu_{n-1}f(\lambda_{n-1}))\) with evaluation points \(\Lambda=\{\lambda_{0},\cdots,\lambda_{n-1}\}\), a parity-check matrix can be taken as the \((n-k)\times n\) Vandermonde matrix \(H=\mathrm{Vand}_{n-k}(\lambda_{0},\cdots,\lambda_{n-1})\), i.e., \[(H)_{t,i}=\lambda_i^t,\qquad t\in[0,n-k-1],\;i\in[0,n-1],\] which satisfies \(H\cdot (c_0,\cdots,c_{n-1})^{\top}=0.\)

In the sequel, when referring to puncturing \(\mathbf{c}\), we adopt a convenient normalization that preserves the Vandermonde structure of the parity-check matrix.

Specifically, let \(\mathcal{P}=\{0,\cdots,n'-1\}\) with \(k<n'<n\), and define \[H|_{\mathcal{P}} := \mathrm{Vand}_{r'}(\lambda_0,\cdots,\lambda_{n'-1}), \quad r'=n'-k,\] by restricting the evaluation points to \(\mathcal{P}\).

To ensure consistency with this reduced parity-check matrix, the codeword symbols are rescaled according to the updated GRS coefficients \[\nu'_i := \prod_{\substack{j\in[0,n'-1]\\ j\neq i}} (\lambda_i-\lambda_j)^{-1}, \quad i\in[0,n'-1].\] Then the rescaled vector \(\big(\nu'_0\nu_0^{-1}c_0,\cdots,\nu'_{n'-1}\nu_{n'-1}^{-1}c_{n'-1}\big)\) satisfies the parity-check equations defined by \(H|_{\mathcal{P}}\).

Therefore, without loss of generality, we assume this scaling is applied locally by each node and treat it implicitly, and represent the punctured codeword as \((c_0,\cdots,c_{n'-1})\) with parity-check matrix \(H|_{\mathcal{P}}\).

2.1 Minimum Storage Regenerating Code↩︎

In distributed storage systems, regenerating codes are designed to efficiently repair failed storage nodes. A data file \(\mathcal{M}\) is encoded and stored across \(n\) storage nodes, and each node stores a vector of length \(\alpha\), i.e. \(\alpha\) subsymbols. When a node fails, a replacement node is generated by downloading \(b\) subsymbols from each of a subset of surviving nodes, referred to as helper nodes. The total amount of subsymbols \(db\) downloaded from \(d\) helper nodes is called repair bandwidth.

In this work, we focus on regenerating codes achieving the minimum storage point, which satisfy the MDS property. Such codes are referred to as minimum storage regenerating (MSR) codes.

For the general cut-set bound, readers may refer to [1].

2.2 Hadamard-Design MSR Code↩︎

We briefly recall the Hadamard-design MSR construction in [13], which supports arbitrary parameters \(n\), \(k\), and \(d\), and will be used later in our constructions.

1. Hadamard-design MSR construction: Consider an \((n,k;\alpha)\) MSR code over \(\mathbb{F}_q\) with \(q>sn\), and define \(s:=d-k+1,\, \alpha:=s^n.\) Let \((\mathbf{c}_0,\cdots,\mathbf{c}_{n-1})\) be a codeword, where \(\mathbf{c}_i=(c_{0,i},\cdots,c_{\alpha-1,i})^{\top}\) for \(i\in[0,n-1]\).

Select \(sn\) distinct elements \[\label{eq:32distinct32points} \{\lambda_{a,j}:a\in[0,s-1],\,j\in[0,n-1]\}\subseteq\mathbb{F}_q.\tag{3}\]

The Hadamard MSR construction is based on structural properties that enable efficient repair. We describe it in two steps.

Step (i) Establish the layered MDS property: For each \(w\in[0,\alpha-1]\), choose elements \(\{\alpha_{w,j}:j\in[0,n-1]\}\subseteq{\mathbb{F}}_{q}\) such that \(\alpha_{w,j}\neq\alpha_{w,j'}\quad\text{for }j\neq j'.\)

Define an array code by parity-check equations \[\label{eq:32had95pc95row} \sum_{j=0}^{n-1}\alpha_{w,j}^{t}c_{w,j}=0,\qquad t\in[0,n-k-1],\, w\in[0,\alpha-1].\tag{4}\] Clearly, each row is a scalar \([n,k]\) MDS code, and thus the full code is an \((n,k;\alpha)\) MDS array code.

Step (ii) Impose coordinate-wise periodicity: Index each row by the \(s\)-ary expansion \(w=(w_{(0)},\ldots,w_{(n-1)})\in[0,s-1]^n.\)

To endow the above MDS array code with the Hadamard structure, define \[\label{eq:32had95row95points95simple} \alpha_{w,j}:=\lambda_{w_{(j)},j},\qquad j\in[0,n-1].\tag{5}\] By 3 , we have \(\lambda_{w_{(j)},j}\neq \lambda_{w_{(j')},j'}\) for \(j\neq j'\).

2. Optimal repair property: Intuitively, 4 guarantees row-wise MDS reliability, while 5 makes each node coefficient depend only on one row digit. This allows us to group rows that differ only in the failed coordinate, so helper interference aligns into one summed subsymbol per helper, whereas the failed-node subsymbols remain distinguishable and can be solved with optimal repair bandwidth.

(i) Single-node repair: Fix a failed node \(j^*\in[0,n-1]\). Let \(D\subseteq[0,n-1]\backslash\{j^*\}\) with \(|D|=d\) be the helper-node set. For each row index \(w\), define the group \[\mathcal{G}(w,j^*):=\{R_w(j^*,a):a\in[0,s-1]\},\] where \(R_w(j^*,a)\) is obtained by replacing the \(j^*\)-th coordinate of \(w\) with \(a\). Clearly, the collection of all distinct groups \(\mathcal{G}(w,j^*)\) form a partition of \([0,\alpha-1]\). By the coordinate-wise periodicity, we have \[\label{eq:32periodicity} \alpha_{R_w(j^*,a),j}= \begin{cases} \lambda_{w_{(j)},j}, & j\neq j^*,\\ \lambda_{a,j^*}, & j=j^*, \end{cases} \quad a\in[0,s-1].\tag{6}\] For each \(t\in[0,n-k-1]\), summing the \(s\) equations in 4 corresponding to all rows in the group \(\mathcal{G}(w,j^*)\) gives \[\small \sum_{j\neq j^*}\lambda_{w_{(j)},j}^{t}\,\sum_{a=0}^{s-1}c_{R_w(j^*,a),j} +\sum_{a=0}^{s-1}\lambda_{a,j^*}^{t}\,c_{R_w(j^*,a),j^*}=0,\] where 6 ensures that the coefficients for \(j\neq j^*\) are invariant within each group. Hence, the repair procedure is given as follows:

• Download: For each \(j\in D\), the \(j\)-th helper node transmits one subsymbol \(\sum_{a=0}^{s-1}c_{R_w(j^*,a),j}\) per row group;

• Repair: The failed node \(j^*\) solves \(s\) unknowns \(\{c_{R_w(j^*,a),j^*}:\,a\in[0,s-1]\}\) per group.

Running over all groups recovers the whole symbol in node \(j^*\), which gives \(b=\frac{\alpha}{s}=\frac{\alpha}{d-k+1},\) meeting the cut-set bound in 2 .

(ii) Multiple-node repair: Compared with part (i), the parameter change here comes from applying the space-sharing technique for multi-node repair. Specifically, we extend \(d-k+h\) instances of the single-node repair construction, so the row index is extended and the sub-packetization becomes \(\alpha=(d-k+h)s^n\). In the multiple-node case, the repair is performed in a centralized manner that collects all downloaded data from helper nodes and recovers the failed symbols. We consider the following repair scheme from [14]. Although originally described for the cooperative repair model, it achieves the centralized cut-set bound once the cooperation phase is removed, as observed in [26].

Index each subsymbol by \((w,z)\) with \(w\in[0,s^n-1]\) and \(z\in[0,d-k+h-1]\). Thus, each node \(u\in[0,n-1]\) stores \[\{c_{w,z,u}: w\in[0,s^n-1],\;z\in[0,d-k+h-1]\},\] where \(w=(w_{(0)},\cdots,w_{(n-1)})\in[0,s-1]^n\) is the \(s\)-ary expansion of \(w\). Here \(\oplus\) denotes addition modulo \(s\).

Let the failed set be \(\mathcal{F}=\{j_1,\cdots,j_h\}\) and \(D\subseteq[0,n-1]\backslash\mathcal{F}\) with \(|D|=d\) be the helper-node set. For each \(w\) and \(l\in[h]\), define \[\small \begin{align} \mathcal{G}(w,j_l):=\{(R_w(j_l,&w_{(j_l)}\oplus a),\,a) : a\in[0,s-2]\}\cup\\ &\{(R_w(j_l,w_{(j_l)}\oplus (s-1)),\,s+l-2) \}, \end{align}\] where these groups form a partition of \([0,\alpha-1]\).

For each \(t\in[0,n-k-1]\), summing all the \(s\) parity-check equations corresponding to all rows in group \(\mathcal{G}(w,j_l)\) gives \[\label{eq:32multi95node32equation}\small \begin{align} &\sum_{a=0}^{s-2}\lambda_{w_{(j_l)}\oplus a,j_l}^{t}\,c_{R_w(j_l,w_{(j_l)}\oplus a),a,j_l}\\ +&\lambda_{w_{(j_l)}\oplus (s-1),j_l}^{t}\,c_{R_w(j_l,w_{(j_l)}\oplus (s-1)),s+l-2,j_l}\\ +&\sum_{j\neq j_l}\lambda_{w_{(j)},j}^{t}\,\big(\sum_{a=0}^{s-2}c_{R_w(j_l,w_{(j_l)}\oplus a),\,a,j}\\ +&c_{R_w(j_l,w_{(j_l)}\oplus (s-1)),s+l-2,j}\big)=0. \end{align}\tag{7}\] Then, by 7 , the repair procedure is given as follows:

• Download: For \(l\in[h]\) and a group \(\mathcal{G}(w,j_l)\), each helper node \(j\in D\) transmits one group-sum \[\small \sum_{a=0}^{s-2}c_{R_w(j_l,w_{(j_l)}\oplus a),a,j}+c_{R_w(j_l,w_{(j_l)}\oplus s-1),s+l-2,j},\] and the \(d\) helper-sums can determine \(d-k+h\) unknowns in this group.

• Repair: The difference from single-node repair is the composition of these unknowns: each group \(\mathcal{G}(w,j_l)\) recovers exactly \(d-k+h\) subsymbols, where

  • \(d-k+1\) subsymbols corresponding to failed node \(j_l\): \[\begin{align} \{c_{R_w(j_l,w_{(j_l)}\oplus a),a,j_l}: \,&a\in[0,s-2]\}\\&\cup\{c_{R_w(j_l,w_{(j_l)}\oplus s-1),s+l-2,j_l}\}. \end{align}\]

  • \(h-1\) subsymbols corresponding to failed nodes \(j_{l'}\), \(l'\in[h]\backslash\{ l\}\): \[\begin{align} \{\sum_{a=0}^{s-2}c_{R_w(j_{l},w_{(j_{l})}\oplus a),a,j_{l'}}+&c_{R_w(j_{l},w_{(j_{l})}\oplus s-1),s+{l}-2,j_{l'}}:\\&l'\in[h]\setminus\{l\}\}. \end{align}\]

Running over all \((w,l)\) and combining all the repaired subsymbols recovers all symbols in \(\{j_1,\cdots,j_h\}\).

Each helper sends one symbol per group, i.e., \(hs^n\) subsymbols in total. Hence the per-helper repair bandwidth is \(b=hs^n=\frac{h\alpha}{d-k+h},\) which meets the centralized multi-node cut-set bound in [16].

3 System Model and Convertible MSR Codes↩︎

This section presents the system model and formalizes convertible MSR codes. We focus on two key abstractions of system reconfiguration: the cost of code conversion and the repair efficiency after conversion. Fig. 1 illustrates the system workflow, and Fig. 2 provides a symbol-level view in the merge regime.

3.1 Motivation: Adaptive Redundancy with Efficient Repair↩︎

Large-scale distributed storage systems encode data across \(n\) storage nodes using an \([n,k]\) erasure code, providing tolerance against up to \(n-k\) simultaneous node failures. Production deployments at Facebook (HDFS-RAID), Google (GFS II), and Microsoft (Windows Azure Storage) rely on such codes to protect petabyte-scale data. In practice, however, storage-node reliability is not static: it varies significantly across device types and over the lifetime of individual devices, following the well-known bathtub curve of infant mortality, useful life, and wearout [27]. This motivates adaptive redundancy, where the system dynamically updates the code parameters from \((n_I,k_I)\) to \((n_F,k_F)\) in response to observed reliability, reducing storage overhead by \(11\%\)–\(44\%\) in production clusters [27].

For the MSR setting considered in this paper, adaptive redundancy must satisfy two requirements simultaneously, as shown in Fig. 1. First, the system should perform efficient code conversion: existing data encoded under the initial MSR codes should be converted into a final codeword while accessing only a small subset of the stored symbols. Second, the resulting final code must still support efficient node repair: after conversion, any failed node in the final stripe should be repaired by contacting \(d\) helper nodes and downloading the minimum amount of data allowed by the MSR repair bound.

Existing convertible-code constructions focus on MDS codes and do not preserve the MSR repair property, while standard MSR codes do not support efficient conversion. This work addresses both requirements simultaneously by constructing convertible MSR codes, which combine efficient MSR-to-MSR conversion with optimal repair of both the initial and final codes.

3.2 Code Conversion Model↩︎

We consider the merge regime, where \(m\) initial codewords encoding disjoint data blocks are converted into a single final codeword. This corresponds to the storage reconfiguration stage in Fig. 1. Specifically, let \(\mathcal{C}_{I_1},\ldots,\mathcal{C}_{I_m}\) be \(m\) initial MSR array codes over \(\mathbb{F}_q\), where \(\mathcal{C}_{I_i}\) is an \((n_{I_i},k_{I_i};\alpha)_q\) code for each \(i\in[m]\). The parameters of the initial codes may be different, which gives the irregular setting. The conversion produces a final codeword of an \((n_F,k_F;\alpha)_q\) MSR code \(\mathcal{C}_F\), where \(k_F=\sum_{i=1}^{m} k_{I_i}.\)

Fig. 2 illustrates this conversion at the symbol level. The dashed boxes represent initial and final stripes, and each square represents one vector symbol. Since we consider array codes, each vector symbol stores \(\alpha\) subsymbols, as indicated by the callout in the figure. Selected read symbols are accessed from the initial stripes and routed to the reconfiguration engine, which executes the conversion procedure \(\sigma\).

During conversion, symbols are classified into three categories:

• Unchanged symbols: symbols that appear identically in both an initial codeword and the final codeword, and are reused directly in the final codeword;

• Read symbols: symbols accessed from the initial codewords as inputs to the conversion procedure \(\sigma\);

• Written symbols: symbols of the final codeword that are newly computed from the read symbols.

The reconfiguration engine in Fig. 2 summarizes the conversion process. It reads the required symbols from the initial stripes, computes new symbols using the conversion procedure \(\sigma\), and generates the final stripe by combining unchanged symbols and newly computed symbols. The objective is to preserve as many unchanged symbols as possible while minimizing the symbols and subsymbols accessed during conversion. These requirements are captured by the access-cost and conversion-bandwidth metrics defined below.

3.3 Formal Definition and Performance Metrics↩︎

The efficiency of conversion is quantified by two metrics. The access cost \(\rho=\rho_R+\rho_W\) counts the total number of symbols touched by the conversion, where \(\rho_R\) is the number of read symbols and \(\rho_W\) is the number of newly written final-code symbols. The conversion bandwidth \(\gamma=\gamma_R+\gamma_W\) measures the total amount of data transferred at the subsymbol level, where \(\gamma_R\) and \(\gamma_W\) are the read and write bandwidths, respectively. Since each vector symbol consists of \(\alpha\) subsymbols, conversion bandwidth captures a finer-grained cost than symbol access. These metrics serve as the design targets for the constructions in this paper, guided by the following lower bounds.

The second requirement in Fig. 1 is that efficient repair must remain available after conversion. In other words, the conversion should not merely produce an MDS final code; it should produce a final code that is still an MSR code. This ensures that once the system transitions to the new code configuration, individual node failures can still be repaired with optimal repair bandwidth. This leads to the following definition.

4 A General Conversion Framework for MDS Array Codes↩︎

Motivated by the scalar MDS convertible code in [19], in this section we present a general conversion framework from \(m\) \((n_{I_i},k_{I_i};\alpha)_q\) MDS array codes, \(i\in[m]\), to an \((n_F,k_F;\alpha)_q\) MDS array code.

Throughout this section, we focus on MDS array codes. Specifically, for each \(i\in[m]\) and each subsymbol index \(w\in[0,\alpha-1]\), the coordinate-wise vector \((c^{(i)}_{w,0},\cdots,c^{(i)}_{w,n_{I_i}-1})\) forms an \((n_{I_i},k_{I_i};1)_q\) scalar MDS codeword. Therefore, the conversion can be carried out row-wise for each fixed \(w\), and the final array code is obtained by stacking all rows.

We first describe the initial-code and final-code setup, and then specify the conversion procedures \(\sigma_1\) and \(\sigma_2\) under different parameter regimes.

Define \(n_F = r_F+\sum_{i=1}^{m} k_{I_i}\) and \(k_F=\sum_{i=1}^{m} k_{I_i}\). An \((m,1)_q\) convertible code \(\mathscr{C}\) consists of the following three parts:

Initial codes: For \(i\in[m]\), choose the initial \((n_{I_i},k_{I_i};\alpha)_q\) MDS array code \(\mathcal{C}_{I_i}\). Let \(\mathbf{c}_i=(\mathbf{c}_{i,0},\ldots,\mathbf{c}_{i,n_{I_i}-1})\) be a codeword of \(\mathcal{C}_{I_i}\).

For each \(w\in[0,\alpha-1]\), the row \((c^{(i)}_{w,0},\cdots,c^{(i)}_{w,n_{I_i}-1})\) is a codeword of an \((n_{I_i},k_{I_i};1)_q\) MDS code with an \(r_{I_i}\times n_{I_i}\) parity-check matrix \(H_{i,w}.\)

Final code: The final code consists of the first \(\sum_{i=1}^m k_{I_i}\) symbols copied from the initial codes and \(r_F\) newly generated symbols.

Define the final code as \[\mathcal{C}_F := \{ \sigma(\mathbf{c}_1,\dots,\mathbf{c}_{m}) : \mathbf{c}_i\in\mathcal{C}_{I_i}, i\in[m] \},\] where \(\sigma\) is a conversion procedure defined as follows.

Conversion procedures: For each fixed row \(w\), the conversion follows three steps: (i) identify the unchanged symbols and read symbols, (ii) compute the written symbols, and (iii) deduce the parity-check matrix of the final code.

We consider the following two parameter regimes:

• Regime I: \(r_F\le \min\{k_{I_i},r_{I_i}\}\) for all \(i\in[m]\), where we use conversion procedure \(\sigma_1\);

• Regime II: \(r_F>\min\{k_{I_i},r_{I_i}\}\) for all \(i\in[m]\), where we use conversion procedure \(\sigma_2\).

We describe the two procedures separately.

• \(\sigma_1:\) Step (i): For each \(i\in[m]\), we define: 1) the unchanged symbols as the first \(k_{I_i}\) symbols, i.e., \(\{\mathbf{c}_{i,j}: j\in[0,k_{I_i}-1]\}\); 2) the read symbols as the symbols indexed from \(k_{I_i}\) to \(k_{I_i}+r_F-1\), i.e., \(\{\mathbf{c}_{i,j}: j\in[k_{I_i}, k_{I_i}+r_F-1]\}\); 3) the written symbols as \(\hat{\mathbf{c}}=(\hat{\mathbf{c}}_0, \hat{\mathbf{c}}_1,\cdots,\hat{\mathbf{c}}_{r_F-1})\), where \(\hat{\mathbf{c}}_j=(\hat{c}_{0,j},\cdots,\hat{c}_{\alpha-1,j})\), \(j\in[0,r_F-1]\).

  Thus, the final codeword can be represented by \[\label{eq:32final95codeword951} \mathbf{c}_F = (\mathbf{c}_1|_{[0,k_{I_1}-1]}, \dots, \mathbf{c}_m|_{[0,k_{I_{m}}-1]}, \hat{\mathbf{c}}).\tag{8}\]

  Step (ii): For each \(i\in[m]\), let \(\mathcal{P}_i=\{0,1,\cdots,k_{I_i}+r_F-1\}\) denote the set consisting of the first \(k_{I_i}\) symbols and an additional \(r_F\) symbols. Since \(\mathcal{C}_{I_i}\) is an MDS code, its punctured code \(\mathcal{C}_{I_i}|_{\mathcal{P}_i}\) is also MDS, and the parity-check matrix of \(\mathcal{C}_{I_i}|_{\mathcal{P}_i}\) can be written as \[\label{eq:32punctured95pc} H_{i,w}|_{\mathcal{P}_i}= [\hat{H}_{i,w}^{(\mathcal{P}_i)} \mid \bar{H}_{i,w}^{(\mathcal{P}_i)}], \quad w\in[0,\alpha-1],\tag{9}\] where \(\hat{H}_{i,w}^{(\mathcal{P}_i)}\) is an \(r_{F}\times k_{I_i}\) matrix corresponding to the first \(k_{I_i}\) symbols, and \(\bar{H}_{i,w}^{(\mathcal{P}_i)}\) is an \(r_{F}\times r_{F}\) invertible matrix corresponding to the remaining \(r_F\) symbols. This gives \[\label{eq:32pc95ic} \begin{align} \hat{H}_{i,w}^{(\mathcal{P}_i)}({c}^{(i)}_{w,0},&\cdots, {c}^{(i)}_{w,k_{I_i}-1})^{\top}=\\ &-\bar{H}_{i,w}^{(\mathcal{P}_i)}({c}^{(i)}_{w,k_{I_i}},\cdots, {c}^{(i)}_{w,k_{I_i}+r_F-1})^{\top}. \end{align}\tag{10}\] Given an \(r_F\times r_F\) invertible matrix \(\hat{H}_w\) to be specified in each construction, the written symbols are computed as \[\label{eqn32conA} \begin{align} (&\hat{{c}}_{w,0},\hat{{c}}_{w,1},\cdots,\hat{{c}}_{w,r_F-1})^\top= \\ &\hat{H}^{-1}_w \sum_{i=1}^{m} \bar{H}_{i,w}^{(\mathcal{P}_i)} \cdot (c^{(i)}_{w,k_{I_i}},\cdots,c^{(i)}_{w,k_{I_i}+r_F-1})^\top. \end{align}\tag{11}\]

  Step (iii): It follows from 8 , 10 , and 11 that the final code \(\mathcal{C}_F\) has parity-check matrix \[\label{eq:32parity95sigma951} H_{F,w}:= [\hat{H}_{1,w}^{(\mathcal{P}_1)}| \cdots| \hat{H}_{m,w}^{(\mathcal{P}_m)} | \hat{H}_w], \,w\in[0,\alpha-1].\tag{12}\] The MDS property of \(\mathcal{C}_F\) is determined by whether \(H_{F,w}\) is the parity-check matrix of an \((n_F,k_F;1)_q\) MDS code for each \(w\).

• \(\sigma_2:\) Step (i): 1) For each \(i\in[m]\), the unchanged symbols and read symbols both consist of the first \(k_{I_i}\) symbols, i.e., \(\{\mathbf{c}_{i,j}: j\in[0,k_{I_i}-1]\}\); 2) The written symbols are defined as \(\hat{\mathbf{c}}=(\hat{\mathbf{c}}_0,\hat{\mathbf{c}}_1,\cdots, \hat{\mathbf{c}}_{r_F-1})\), where \(\hat{\mathbf{c}}_j=(\hat{c}_{0,j}, \cdots,\hat{c}_{\alpha-1,j})\), \(j\in[0,r_F-1]\).

  The final codeword is still given by 8 .

  Step (ii): For each \(w\in[0,\alpha-1]\), write the parity-check matrix of \(\mathcal{C}_{I_i}\) as \(H_{i,w}=[\hat{H}_{i,w}\mid\bar{H}_{i,w}]\), where \(\hat{H}_{i,w}\) is an \(r_{I_i}\times k_{I_i}\) matrix and \(\bar{H}_{i,w}\) is an \(r_{I_i}\times r_{I_i}\) invertible matrix. Let \(\hat{H}_{i,w}^E\) be an \(r_F\times k_{I_i}\) matrix obtained from \(\hat{H}_{i,w}\) by appending \(r_F-r_{I_i}\) additional rows.

  The written symbols are computed as \[\label{eqn32conA95rF95gt}\small \begin{align} (\hat{{c}}_{w,0},\hat{{c}}_{w,1},&\cdots,\hat{{c}}_{w,r_F-1})^\top =\\ &- \hat{H}_w^{-1} \sum_{i=1}^{m} \hat{H}_{i,w}^E \cdot ({c}^{(i)}_{w,0},\cdots,{c}^{(i)}_{w,k_{I_i}-1})^{\top}, \end{align}\tag{13}\] where \(\hat{H}_w\) is an \(r_F\times r_F\) invertible matrix.

  Step (iii): With the written symbols computed as in 13 and the final codeword 8 , the final code \(\mathcal{C}_F\) has parity-check matrix \[H_{F,w}:= [\hat{H}_{1,w}^{E}| \cdots| \hat{H}_{m,w}^{E}| \hat{H}_w], \quad w\in[0,\alpha-1].\] The MDS property of \(\mathcal{C}_F\) is determined by whether \(H_{F,w}\) is the parity-check matrix of an \((n_F,k_F;1)_q\) MDS code for each \(w\), as specified in Lemma 1.

The above framework enables row-wise conversion, where each row is treated as a scalar MDS code and stacked to form the array code.

The next lemma follows directly from Theorem 4 in [19] via row-wise application. Specifically, for each fixed subsymbol index \(w\), the setting is scalar, and thus the corresponding scalar MDS and scalar access-optimal results apply. Hence, if each row code is MDS, then stacking all rows yields the array-code MDS property. Similarly, if each row conversion is scalar access-optimal, then summing over all rows yields array-level access optimality, since access cost is measured in symbols. Therefore, the proofs are omitted for brevity.

5 Array MSR-to-MSR Conversion↩︎

In this section, we consider \((m,1)_q\) convertible MSR array codes. We first address the irregular setting, where the initial codes may have different parameters. Building on this, we further consider the practically motivated same-code setting, where all initial codewords are drawn from the same MSR code.

5.1 Irregular Constructions↩︎

We begin with the irregular setting, where the \(m\) initial codes \(\mathcal{C}_{I_i}\) for \(i\in[m]\) are Hadamard-based MSR codes, which may have different parameters \((n_{I_i},k_{I_i};\alpha)\). Building on the conversion framework established in Section 4, we construct \((m,1)_q\) convertible MSR codes achieving optimal access cost.

The main challenge arises from a structural mismatch between MSR repair and code conversion. In a Hadamard MSR code, the coefficient at node \(u\) depends on \(w\) only through the \(u\)-th coordinate \(w_{(u)}\), which is the key property enabling interference alignment during repair. However, when multiple Hadamard MSR codes are merged directly via conversion, the resulting final code does not inherit this property: different nodes in the final code end up sharing the same coordinate dependence, violating the coordinate-wise periodicity required for MSR repair.

To address this issue, we design the initial codes with a subsymbol-level structure such that the required periodicity is preserved under conversion. More precisely, we observe that the periodicity required by the final code can be embedded into the initial codes at the design stage, by arranging their subsymbol-level structure according to the parameters of the final code. As we will show, this pre-alignment does not compromise the MSR repair properties of the initial codes, and ensures that the required periodic structure is automatically inherited by the final code after conversion. An example is given below.

We now introduce the notation used in the construction. For \(i\in[m]\), let \(\mathcal{P}_i:=\{0,1,\cdots,k_{I_i}+r_F-1\}\). For any \(w\in[0,s^L-1]\), recall that \(w_{(u)}\) denotes the \(u\)-th coordinate in the \(s\)-ary expansion of \(w\). Let \(k_{I_i}<d_{I_i}\leq n_{I_i}-1\) and \(k_F<d_F\leq n_F-1\) denote the numbers of helper nodes used for single-node repair in \(\mathcal{C}_{I_i}\) and \(\mathcal{C}_F\), respectively. In both codes, any single-node failure can be repaired with optimal repair bandwidth. According to the lower bound on access cost given in Theorem 1, we consider two parameter regimes: \(r_F \leq \min\{k_{I_i}, r_{I_i}\}\) and \(r_F > \min\{k_{I_i}, r_{I_i}\}\) for all \(i\in[m]\).

In the following constructions, we only specify the initial codes, the conversion procedure, and the matrix \(\hat{H}_w\) for the final code; the remaining components follow directly from the framework in Section 4.

5.2 Same-Code Constructions↩︎

In this subsection, we construct \((m,1)_q\) convertible MSR array codes for the setting where the \(m\) initial codewords are drawn from a common \((n_I,k_I;\alpha)_q\) MSR code \(\mathcal{C}_I\). This setting is motivated by practical storage systems, which typically operate with a single uniformly deployed erasure code. When storage requirements change—due to data growth, node addition, or fault-tolerance adjustments—the system must convert multiple codewords of the same code into a new code. Concretely, the conversion procedure transforms \(m\) codewords of \(\mathcal{C}_I\) into a codeword of an \((n_F,k_F;\alpha)_q\) MSR code \(\mathcal{C}_F\).

In the irregular setting, since the initial codes can be designed independently, the required periodic structure can be embedded at the design stage. However, when all initial codewords are drawn from the same code, the initial codes share a common structure that must be uniformly applied to all codewords. In this case, we introduce a row-matching technique that achieves the required alignment through a bijective row remapping in the conversion procedure itself, rather than at the design stage.

5.2.1 Illustrative Examples↩︎

The following example shows that the irregular construction in Section 5 cannot produce two initial codewords from the same code, motivating the need for a different approach.

To resolve this issue, we introduce the row-matching technique, which applies a bijective row remapping \(\pi_i\) to each initial codeword before conversion. The key idea is to pair rows from the same MSR code across the initial codewords so that, after conversion, the resulting final code recovers the periodic structure required for MSR repair. The following example illustrates this approach.

The examples above illustrate the key ideas behind the row-matching technique. We now formalize this approach.

5.2.2 The Row-Matching Technique↩︎

Let \(\mathcal{C}_{I}\) be the initial code, which is an \((n_I,k_I;s^L)_q\) Hadamard-based MSR code whose row coefficients are given by \(\alpha_{w,u}:=\lambda_{w_{(u)},u},\quad u\in[0,n_I-1],\,w\in[0,s^L-1].\)

Step 1: Scale the evaluation points. For each \(i\in[m]\), define a code \(\mathcal{C}_{I_i}\) with row coefficients \(\delta_i\alpha_{w,u}=\delta_i\lambda_{w_{(u)},u},\, u\in[0,n_I-1],\,w\in[0,s^L-1],\) where \(\delta_i\in\mathbb{F}_q^*\) is a nonzero scalar such that the scaled sets \[\label{eq:32scaled95Set} \Lambda^{(i)}_{k_I}:=\{\delta_i\lambda_{v,u}:v\in[0,s-1],\, u\in[0,k_I-1]\}\tag{14}\] are pairwise disjoint. Then, the parity-check equations of \(\mathcal{C}_{I_i}\) are given by \[\small \begin{align} \sum_{u=0}^{n_I-1}(\delta_i\lambda_{w_{(u)},u})^t c^{(i)}_{w,u}=\delta_i^t\sum_{u=0}^{n_I-1}\lambda_{w_{(u)},u}^t c^{(i)}_{w,u}=0,\\ \quad t\in[0,r_I-1],\,w\in[0,s^L-1], \end{align}\] which differ from those of \(\mathcal{C}_I\) only by the common scaling factor \(\delta_i^t\). Since multiplying all evaluation points by a common nonzero scalar does not change the solution set of the parity-check equations, all \(\mathcal{C}_{I_i}\) represent the same MSR code \(\mathcal{C}_I\). Furthermore, the disjointness condition on the first \(k_I\) evaluation points ensures that the unchanged symbols from different initial codes do not collide, which is required for the MDS property of the final code.

Step 2: Define the row-matching maps. For each \(i\in[m]\), let \(\pi_i:[0,\alpha-1]\to[0,\alpha-1]\) be a bijection. We set \(\pi_1(w)=w\), leaving the first codeword unchanged, and for \(i\geq 2\) define \(\pi_i\) as a cyclic left-shift of the \(s\)-ary expansion of \(w\) by \((i-1)k_I\) positions: \[\label{eq:32row95matching32mapping} \begin{align} \pi_i(w_{(0)},\cdots,&w_{(L-1)}):=\\ (w_{((i-1)k_I)},\cdots,&w_{(L-1)},w_{(0)},\cdots,w_{((i-1)k_I-1)}). \end{align}\tag{15}\] Since each \(\pi_i\) is induced by a coordinate permutation of the \(s\)-ary expansion of \(w\), it is a bijection on \([0,\alpha-1]\). By 15 , the \(u\)-th coordinate of \(\pi_i(w)\) satisfies \(\pi_i(w)_{(u)}=w_{(u+(i-1)k_I)}\), so the parity-check equations of the \(i\)-th codeword at row \(\pi_i(w)\) take the form \[\small \sum_{u=0}^{n_I-1}\lambda_{w_{(u+(i-1)k_I)},\,u}^t\, c^{(i)}_{\pi_i(w),u}=0,\] which is precisely ?? in Construction 1. Hence the row-matching converts the same-code conversion into an instance of Construction 1, and the MSR repair properties of both the initial codes and the final code follow directly from Theorem 3.

Step 3: Apply the conversion framework. For each \(w\in[0,\alpha-1]\), the \(m\) rows \[\small \big(c^{(i)}_{\pi_i(w),0},\cdots,c^{(i)}_{\pi_i(w),n_I-1}\big), \quad i\in[m],\] are grouped together to form one scalar conversion instance, and the remaining conversion steps follow exactly those in Section 4.

5.2.3 Same-Code Convertible MSR Codes↩︎

The row-matching technique applies to any Hadamard-based MSR code \(\mathcal{C}_I\) with sufficiently large \(L\) and field size \(q\), yielding convertible MSR codes in which all initial codewords are drawn from the same code. We now instantiate this procedure using Construction 1 and Construction 1A. As we will show, the same-code constraint does not incur any loss: the resulting codes achieve optimal access cost and optimal conversion bandwidth in the corresponding parameter regimes.

Since all initial codewords are drawn from \(\mathcal{C}_I\), the parameters satisfy \(n_{I_i}=n_I\), \(k_{I_i}=k_I\), and \(r_{I_i}=r_I\) for all \(i\in[m]\), and the sub-packetization parameter simplifies to \(s=\mathrm{lcm}(d_I-k_I+1,\,d_F-k_F+1)\). We next specialize the above three-step procedure to the same-code setting.

Step 1 (Scaling). We take \(\mathcal{C}_I=\mathcal{C}_{I_1}\), thus row coefficients are given by \[\label{eq:32c95195coefficient} \alpha_{w,u}:=\lambda_{w_{(u)},u}=\beta^{su+w_{(u)}},\quad u\in[0,n_I-1].\tag{16}\]

For each \(i\in[m]\), set \(\delta_i:=\beta^{(i-1)sk_I}\). The row coefficients of \(\mathcal{C}_{I_i}\) are then \[\delta_i\lambda_{w_{(u)},u}=\beta^{s((i-1)k_I+u)+w_{(u)}}, \quad u\in[0,n_I-1],\] and all \(\mathcal{C}_{I_i}\) represent the same MSR code \(\mathcal{C}_I\). By 14 and 16 , we can deduce that the scaled sets \[\small \Lambda_{k_I}^{(i)}=\bigl\{\delta_i\beta^{su+v}:v\in[0,s-1],\, u\in[0,k_I-1]\bigr\}\] are pairwise disjoint.

Step 2 (Row-matching). For each \(i\in[m]\), apply the bijection \(\pi_i\) defined in 15 to the rows of \(\mathcal{C}_{I_i}\).

Step 3 (Conversion). For each \(w\in[0,\alpha-1]\), row \(\pi_i(w)\) of \(\mathcal{C}_{I_i}\) serves as the \(i\)-th input to the conversion procedure in Section 4, with \(\hat{H}_w\) given by ?? for Construction 1 and by ?? for Construction 1A. The parity-check equations of the resulting final code \(\mathcal{C}_F\) are \[\label{eq:32step395final}\small \begin{align} \sum_{i=1}^m\sum_{u=0}^{k_I-1}\!&\left(\beta^{s((i-1)k_I+u) +\pi_i(w)_{(u)}}\right)^{\!t}\!c_{w,(i-1)k_I+u} +\\&\sum_{u=0}^{r_F-1}\!\left(\beta^{s(mk_I+u)+w_{(mk_I+u)}} \right)^{\!t}\!c_{w,mk_I+u}=0, \end{align}\tag{17}\] for \(t\in[0,r_F-1]\) and \(w\in[0,\alpha-1]\). By 15 , the row-matching bijection satisfies \[\pi_i(w)_{(u)}=w_{((i-1)k_I+u)},\quad i\in[m],\,u\in[0,n_I-1].\] Substituting into 17 yields \[\small \sum_{u=0}^{n_F-1}\left(\beta^{su+w_{(u)}}\right)^t c_{w,u}=0, \quad t\in[0,r_F-1],\;w\in[0,\alpha-1],\] which is precisely the Hadamard MSR structure in 5 . Hence \(\mathcal{C}_F\) is an MSR code.

Moreover, since all initial codes share the same parameters, the conversion bandwidth lower bound in Theorem 2 applies. Construction 1 achieves this bound for \(r_F\leq\min\{k_I,r_I\}\), and Construction 1A achieves it for \(r_F>k_I\). We summarize as follows.

To achieve the bound ?? , we instead use \(\sigma_1\) augmented with the multi-node repair scheme of Section 2.2 (ii), as detailed in Stages 1 and 2 of Construction 2 below. This reduces the conversion bandwidth at the cost of reading additional symbols beyond the \(mk_I\) nodes. In fact, achieving the bandwidth lower bound ?? in this regime inherently requires contacting more than \(mk_I\) nodes, which exceeds the access lower bound. Hence access-optimality and bandwidth-optimality are fundamentally incompatible in this regime, and we focus on bandwidth-optimal constructions. In particular, we set \(d_F=k_F+r_I\).

Since this construction uses the multi-node repair scheme of Section 2.2 (ii), a space-sharing extension of the subpacketization is required. We index each row by a pair \((w,z)\) with \(w\in[0,s^L-1]\) and \(z\in[0,r_F-1]\), so that \(\alpha=r_Fs^L\). The index \(w\) carries the periodic structure required for MSR repair and row-matching, while \(z\) indexes the space-sharing instances. The row-matching maps \(\pi_i\) act only on \(w\), leaving \(z\) unchanged.

6 Conclusion↩︎

In this paper, we studied convertible MSR codes in the merge regime and proposed explicit MSR-to-MSR conversion schemes that jointly achieve efficient conversion and optimal repair. Our constructions attain optimal access cost, optimal conversion bandwidth, and the MSR repair property. These results provide a unified approach to combining conversion efficiency and repair optimality in distributed storage systems.

References↩︎

---

1. Y. Yang, H. Cai, X. Lei and X. Tang are with the Information Coding and Transmission Key Laboratory of Sichuan Province, Southwest Jiaotong University, Chengdu 610032, China (email: yangyumeng@my.swjtu.edu.cn, hancai@swjtu.edu.cn, xflei@swjtu.edu.cn, xhutang@swjtu.edu.cn).↩︎