Rack-aware storage systems organize the storage nodes in racks such that the cross-rack communication cost is much more expensive than the intra-rack communication cost. In this paper, we primarily investigate the cross-rack update bandwidth defined as the average amount of symbols transferred across different racks during an update process of one single node. It is critical to design erasure codes that minimize the cross-rack update bandwidth. Our main contributions are as follows. First, we establish the model of cross-rack update bandwidth of irregular array codes over rack-aware storage systems. Second, we derive the tight lower bound on cross-rack update bandwidth, and define minimum cross-rack update bandwidth (MCUB) codes as the irregular array codes that can achieve our tight lower bound. Third, we derive the tight lower bound on redundancy defined as the total number of parity symbols for MCUB codes, and define minimum redundancy MCUB (MR-MCUB) codes as the MCUB codes that can achieve the redundancy lower bound. Fourth, we present explicit constructions of MR-MCUB codes that achieve both the minimum cross-rack update bandwidth and the minimum redundancy, which means that the two lower bounds are tight. Last, we define intra-rack update bandwidth as the average amount of symbols incurred within one rack in an update process, and derive the lower bound of intra-rack update bandwidth of MCUB codes. Moreover, we show that our MCUB codes constructions can also achieve the lower bound of intra-rack update bandwidth.

Polynomial remainder codes form a class of linear codes constructed based on the Chinese Remainder Theorem over polynomial rings, with Reed-Solomon codes as a special case. In particular, irreducible polynomial remainder codes are those where the moduli are pairwise coprime irreducible polynomials. This paper presents an efficient encoding and decoding method for irreducible polynomial remainder codes over F2m, leveraging the additive Fast Fourier Transform (additive FFT). The proposed approach achieves a computational complexity ofO(Nlog2(N−K)), whereNandKdenote the code length and dimension, with the additional requirement thatN−Km−1andN−Kis a power of 2. This substantially outperforms the best known algorithm for such codes, which has a complexity ofO(N2). Furthermore, we conduct a non-asymptotic complexity comparison under specific parameters, with numerical results demonstrating that the proposed algorithms effectively reduces computational complexity. For example, with code lengthN= 256 and dimensionK= 224, our method achieves an approximately 83% reduction in multiplicative complexity for encoding and a 50% reduction for decoding compared to the state-of-the-art approach for polynomial remainder codes.

Analog error-correcting codes (Analog ECCs) can effectively detect and correct computational errors generated during vector-matrix multiplication in the real domain. Recently, several related classes of single-error and multiple-error Analog ECCs have been proposed. However, most existing constructions encounter limitations such as high storage overhead, limited code length range, and high decoding complexity, which diminish their practical applicability. In this paper, we first propose a new framework for generating MDS Analog ECCs with arbitrary code length for single-error detection and correction. Utilizing this framework, we propose a new decoding algorithm for our codes with lower decoding complexity than the existing decoding method. We divide decoding algorithm into two parts: syndrome calculation and error correction. We show that the error correction complexity of our method which is explicit is$O(\log (n))$, while the error correction complexity of existing decoding method based on geometric features which is not explicit is at least$O(n)$, here$n$represents the code length. Simulation experiments demonstrate that our decoding algorithm maintains a high error correction success rate for correcting a single outlying error, even when the error scale is significantly below our established theoretical threshold.

Piggybacking codes have garnered extensive research attention for their potential to reduce the repair bandwidth of traditional maximum distance separable (MDS) codes. The existing piggybacking codes are only considered for improving the repair performance for single-node erasure. In this paper, we propose a new piggybacking code construction with a small sub-packetization level. Through carefully designed piggyback functions, our code can effectively reduce the repair bandwidth for both single-node and double-node erasures. Specifically, we show that when$r$is large and$r \ll k$(here,$r$represents the number of parity nodes and$k$represents the number of data nodes), our code can achieve a reduction in the average repair bandwidth for double-node erasure by approximately 33 %, and for single-node erasure by around 50 %, when compared to the traditional MDS property-based repair method. To our knowledge, this is the first exploration for efficient repair of multi-node erasure under the piggybacking framework.

Matrix multiplication over the real field constitutes a foundational operation in the training of deep learning models, serving as a computational cornerstone for both forward and backward propagation processes. However, the presence of silent data corruption (SDC) in large-scale distributed training environments poses a significant threat to model convergence and predictive accuracy, particularly when such errors manifest during matrix multiplication. Due to their transient and non-intrusive nature, these errors often evade detection, allowing them to propagate and accumulate over time, ultimately leading to substantial degradation in model performance. In this paper, we introduce a novel error-correcting coding framework specifically tailored for matrix multiplication operations. Our proposed framework is designed to detect and correct multiple computational errors that may arise during the execution of matrix products. By leveraging a grid-based structural encoding scheme, our approach enhances error localization and correction capabilities across all participating matrices, thereby significantly improving the fault tolerance of the computation. Experimental results demonstrate that our method achieves deterministic correction of up to two erroneous symbols distributed across three matrices with 100% reliability, while incurring only a 24% overhead in computational time on GPU architectures. Furthermore, we provide a rigorous theoretical analysis of the error-correction properties inherent to our coding scheme, establishing its correctness and robustness under well-defined fault models.

Piggybacking codes are a class of maximum distance separable (MDS) array codes that can achieve repair bandwidth reduction of single-node erasure by adding some piggyback functions to a subset of parity symbols. However, the repair bandwidth reduction is limited since the number of parity symbols the piggyback function can be added should be strictly less than a value to maintain the MDS property. In this paper, we first propose a new transformation on parity nodes that can effectively reduce the repair bandwidth of parity nodes, and the MDS property can still be maintained without changing the field size of the base code. Combined with the new transformation, we jointly design piggyback functions to reduce the repair bandwidth of data nodes. Since the new transformation no longer obeys the constraints under the piggybacking framework, we call the newly obtained codes aspiggybacking+codes. We theoretically show that the repair bandwidth of the piggybacking+ code is strictly lower than that of the existing piggybacking codes at high-code-rate parameters. We also show that our piggybacking+ codes have 3% to 29% repair bandwidth reduction than the existing piggybacking codes for the evaluated high-code-rate parameters.

In data centers, storage nodes are typically organized in racks and rack-aware regenerating codes (RRCs) can achieve the optimal trade-off between storage capacity and cross-rack repair bandwidth. In this paper, we present explicit constructions for multiple erasure tolerance of rack-aware regenerating codes (MET-RRCs), i.e., RRCs with optimal cross-rack repair bandwidth for multi-node failures. We refine the MET-RRC framework in [2] under more extensive parameters and extend the existing construction methods of RRCs. Specifically, we leverage the parity-check matrix structure to present a general framework for multiple erasure tolerance of minimum storage rack-aware regenerating (MET-MSRR) codes. The existing parity-check matrix construction of MSRR codes can be elucidated with this framework. Moreover, we present the construction for multiple erasure tolerance of minimum bandwidth rack-aware regenerating (MET-MBRR) codes using the product-matrix framework.

Reed-Solomon (RS) codes are widely used to correct errors in storage systems. Finding the error locator polynomial is one of the key steps in the error correction procedure of RS codes. Modular Approach (MA) is an effective algorithm for solving the Welch-Berlekamp (WB) key-equation problem to find the error locator polynomial that needs$2t$steps, wheretis the error correction capability. In this paper, we first present a new MA algorithm that only requires$2e$steps and then propose two fast decoding algorithms for RS codes based on our MA algorithm, whereeis the number of errors and$e\leq t$. We propose the Improved-Frequency Domain Modular Approach (I-FDMA) algorithm that needs$2e$steps to solve the error locator polynomial and present our first decoding algorithm based on the I-FDMA algorithm. We show that, compared with the existing methods based on MA algorithms, our I-FDMA algorithm can effectively reduce the decoding complexity of RS codes when$e\lt t$. Furthermore, we propose the$t_{0}$-Shortened I-FDMA ($t_{0}$-SI-FDMA) algorithm ($t_{0}$is a predetermined even number less than$2t-1$) based on the new termination mechanism to solve the error numberequickly. We propose our second decoding algorithm based on the SI-FDMA algorithm for RS codes and show that the multiplication complexity of our second decoding algorithm is lower than our first decoding algorithm (the I-FDMA decoding algorithm) when$2e\lt t_{0}+1$.

Reed-Solomon (RS) codes are widely used to correct errors, finding the error locator polynomial is one of the key steps in the error correction procedure of RS codes. Modular Approach (MA) is a classical algorithm to solve the Welch-Berlekamp (WB) key-equation problem to find the error locator polynomial that needs$2t$steps, where$t$is the error correction capability. In this paper, we present a new MA algorithm that only requires$2e$steps, where$e$is the number of errors. Moreover, we propose a new error correction algorithm based on our MA algorithm, which is called the Improved-Frequency Domain Modular Approach (I-FDMA) algorithm. We show that, compared with the existing methods based on MA algorithms, our I-FDMA algorithm can effectively reduce the decoding complexity of RS codes when$e < t$.

Erasure codes have been widely employed in distributed storage systems to provide high data reliability at a cost of small redundancy. Modern distributed storage systems usually organize the storage nodes in racks, in which the cross-rack communication cost is much more expensive than the intra-rack communication cost. When the original data symbols stored in a single node are updated, it is critical to design erasure codes that can update the corresponding coded symbols with the cross-rack update bandwidth defined as the average amount of symbols transferred across different racks as small as possible. In this paper, we first derive a tight lower bound on the cross-rack update bandwidth under the condition of$(n, k)$reconstruction property that is any$k$out of the$n$nodes can retrieve all the data symbols. Moreover, we derive the lower bound on redundancy subject to the minimum cross-rack update bandwidth. Furthermore, we propose explicit constructions that can achieve both the minimum cross-rack update bandwidth and the minimum redundancy.

Reed-Solomon (RS) codes are constructed over a finite field that have been widely employed in storage and communication systems. Many fast encoding/decoding algorithms such as fast Fourier transform (FFT) and modular approach are designed for RS codes to reduce the encoding/decoding complexity defined as the number of XORs involved in the encoding/decoding procedure. In this paper, we present the construction of RS codes over the cyclic polynomial ring$\mathbb{F}_{2}[x]/(1+x+\ldots+x^{p-1})$and show that our codes are maximum distance separable (MDS) codes. Moreover, we propose the FFT and modular approach over the ring that can be employed in our codes for encoding/decoding complexity reduction. We show that our codes have 17.9% encoding complexity reduction and 7.5% decoding complexity reduction compared with RS codes over finite field, for$(n,k)$= (2048, 1984).

Maximum distance separable (MDS) codes facilitate the achievement of elevated levels of fault tolerance in storage systems while incurring minimal redundancy overhead. Reed-Solomon (RS) codes are typical MDS codes with the sub-packetization level being one, however, they require large repair bandwidth defined as the total amount of symbols downloaded from other surviving nodes during single-node failure/repair. In this paper, we present the set transformation, which can transform any MDS code into set transformed code such that (i) the sub-packetization level is flexible and ranges from 2 to$(n-k)^{\lfloor\frac{n}{n-k}\rfloor}$in which$n$is the number of nodes and$k$is the number of data nodes, (ii) the new code is MDS code, (iii) the new code has lower repair bandwidth for any single-node failure. We show that our set transformed codes have both lower repair bandwidth and lower field size than the existing related MDS array codes, such as elastic transformed codes [1]. Specifically, our set transformed codes have 2% - 6.6% repair bandwidth reduction compared with elastic transformed codes [1] for the evaluated typical parameters.

Reed-Solomon (RS) codes are widely used in storage systems to ensure data reliability. In this paper, we first propose a new construction of RS codes with between three to five parity symbols over a special finite field of size 256. We show that all the operations involved in the encoding/decoding process can be implemented by XOR and cyclic shift. Second, we present a fast encoding/decoding algorithm for our codes by designing a modified Reed-Muller (RM) transform that has both small computational complexity and space complexity. We show that our codes have much lower space complexity and nearly the same computational complexity, compared with the existing RM-based RS codes. Simulation results demonstrate that our codes improve encoding and decoding throughput by 34.06% and 31.66%, respectively, under evaluated parameters, compared with existing RM-based RS codes.

The I/O cost, i.e., the total number of symbols to be read during the single node failure/repair process in a distributed storage system, is one of the most important metrics in repairing Reed-Solomon (RS) codes by the linear repair scheme. In this paper, we construct a linear repair scheme that is applicable to arbitrary$(n,\ k)$RS codes. We show that most existing repair schemes of RS codes can be viewed as a special case of our repair scheme.

As maximum distance separable (MDS) array codes, piggybacking codes can effectively reduce the repair bandwidth of traditional MDS codes for single-node failure with small sub-packetization. However, the requirement of maintaining MDS property over small field size imposes severe restrictions on the design of piggyback functions in the piggybacking framework, which limits the reduction of repair bandwidth. In this paper, we propose conjugate-piggybacking codes over a small sub-packetization level. We design conjugate transformation for piggyback functions in our codes, which enables some parity nodes to achieve optimal repair bandwidth. We show that our codes are MDS codes over a slightly larger field size than the existing related piggybacking codes. We also show that our codes have lower repair bandwidth than the existing related piggybacking codes under evaluated high-code-rate parameters and$\mathbb{F}_{2^{8}}$.

As a special class of array codes, piggybacking codes are maximum distance separable (MDS) codes that can achieve low repair bandwidth for single-node erasure. An (n,k,m) piggybacking code containskdata nodes andr=n-kparity nodes, each node storesmsymbols. In this paper, we propose a new piggybacking design by jointly designing piggyback functions for both data node repair and parity node repair to reduce the repair bandwidth. Our piggybacking codes can support flexible sub-packetizationmwith 2 ≤m≤r. Whenm=r, we derive a new lower bound of repair bandwidth based on our piggybacking structure and show that this lower bound is lower than the corresponding lower bounds derived from the existing piggybacking codes for 5r≪k. Whenmr, we show that our piggybacking codes have lower repair bandwidth than the existing piggybacking codes for all the evaluated high-code-rate parameters with 10 ≤r≤ 20,k= 100 andm≤ 5. Moreover, we derive the lower bound of repair complexity defined as the number of multiplication operations required in repairing single-node erasure under general piggybacking framework and show that our codes can achieve the repair complexity lower bound, i.e., our codes have optimal repair complexity.

Maximum distance separable (MDS) codes have the optimal trade-off between storage efficiency and fault tolerance, which are widely used in distributed storage systems. As typical non-MDS codes, simple regenerating codes (SRCs) can achieve both smaller repair bandwidth and smaller repair locality than traditional MDS codes in repairing single-node erasure. In this paper, we propose generalized simple regenerating codes (GSRCs) that can support much more parameters than that of SRCs. We show that there is a trade-off between sub-packetization and fault tolerance in our GSRCs, and SRCs achieve a special point of the trade-off of GSRCs. We show that the fault tolerance of our GSRCs increases when the sub-packetization increases linearly. We also show that our GSRCs can locally repair any single-symbol erasure and any single-node erasure, and the repair bandwidth of our GSRCs is smaller than that of the existing related codes.

As a special class of array codes,$(n,\ k,\ m)$piggy-backing codes are$n\times m$MDS array codes with each node storing$m$symbols that can achieve low repair bandwidth for single-node failure. The existing piggybacking codes design piggyback functions for either data node repair or parity node repair. In this paper, we propose new piggybacking codes by jointly designing piggyback functions for both data node repair and parity node repair that have lower repair bandwidth than the related existing piggybacking codes. In our piggybacking codes, the sub-packetization$m$satisfies that$2\leq m\leq n-k$. When$m=n-k$, we derive a lower bound of repair bandwidth for our piggybacking codes, and prove that this lower bound is lower than the corresponding lower bounds of the existing piggybacking codes for$5 < n-k\ll k$. When$m < n-k$, we show that our piggybacking codes have lower repair bandwidth than the existing piggybacking codes for all the evaluated high-code-rate parameters with$10 < n-k < 20, k=100$and$m\leq 5$.

In distributed storage systems, storage nodes are organized in racks in which the cross-rack communication cost is much more expensive than the intra-rack communication cost. It is critical to design erasure codes that minimize the cross-rack update bandwidth which is defined as the total amount of symbols transferred across different racks during an update process. In this paper, we analyze the cross-rack update bandwidth of erasure codes for distributed storage systems. We derive a lower bound on the cross-rack update bandwidth and show that the proposed lower bound is achievable under certain parameters.

Piggybacking codes are a class of maximum distance separable (MDS) array codes that can achieve repair bandwidth reduction of single-node failure by adding some piggyback functions in a subset of parity symbols. However, the repair bandwidth reduction is limited since the number of parity symbols of which the piggyback function can be added should be strictly less than a value in order to maintain the MDS property. In this paper, we present a new class of MDS array codes, call piggybacking+ codes with linear sub-packetization level and small finite field that can achieve lower repair bandwidth compared with the existing piggybacking codes. We show that our piggybacking+ codes have 3% to 29% repair bandwidth reduction of the existing piggybacking codes for the evaluated high -code- rate parameters. Our main idea is that we design piggyback functions for data node repair and transformation functions for parity node repair such that the number of parity symbols which can add piggyback function or transformation function is larger than that of the existing piggybacking codes.

Piggybacking codes are an important class of array codes with small sub-packetization to achieve small repair bandwidth for single-node failures. In this paper, we propose new piggybacking codes such that the sub-packetization is equal to the number of parity nodes. Our piggybacking codes have an efficient repair method for any single-node failure, including both data nodes and parity nodes. We show that the proposed piggybacking codes have strictly less repair bandwidth for any single-node failure than that of the existing piggybacking codes, when the code rate is k/n = 0.8, 0.9 and the number of parity nodes ranges from 6 to 40.

Piggybacking is a class of coding framework for MDS array codes that can achieve small repair bandwidth with small sub-packetization. An ($n, k, \alpha$) piggybacking code can be represented by an$n\times \alpha$array such that each node (row) stores$\alpha$symbols and any$k$rows can retrieve all$k\alpha$data symbols. In this paper, we first propose a new piggybacking framework for MDS array codes with lower sub-packetization and then propose two specific piggybacking codes based on the proposed framework. We show that the average repair bandwidth of any single-node failure of our piggybacking codes is lower than all the existing piggybacking codes with the same parameters when the sub-packetization is small (usually$\alpha\leq 8$) and$n-k\geq 10$.