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.

In this paper, we propose a new decoding algorithm for extremely skewed distribution, so that it can omit reading unnecessary bits and thus improve decoding performance. In particular, the proposed method does not require additional space to store the encoded stream. Specifically, we first reorder the compressed bit sequence as in [1], so that to support direct access without extra space. Then, we propose a labeling method to generate a temporary label corresponding to the encountered block, in order to indicate whether the length of the codeword stored in that block is determined. If it is determined, we can identify where to read the necessary bits for decoding the desired symbol. Otherwise, we read bits from the later blocks to update the labels until the codeword lengths are determined.

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$.

Theq-ary maximum distance separable (MDS) array codes, especiallyq= 2v, have important applications in the storage systems to prevent data loss. At now, almost all algebraic constructions of such codes are carried out over the quotient ring Rm= Fq[x]/⟨xm+1⟩ or its subring Fq[x]/⟨xm−1+xm−2+· · ·+1⟩. In this paper, we consider the construction of MDS array codes derived form Rm,λ= Fq[x]/⟨xm+ λ⟩, where λ ∈ F∗q= Fq\{0}, gcd(m, q) = 1. By giving λ-GCD Constraint of polynomials and the punctured λ-twisted circulant matrices, a generic construction and its extensions of such codes are presented. Under this framework, four new explicit constructions are also provided. Specifically, some low-density MDS array codes are obtained in Explicit Constructions I and I ′ . Explicit Constructions II and III provide long MDS array codes that can be applied in the large-scale storage systems. Explicit Construction IV gives MDS array codes both with the optimal repair bandwidth and the lowest update complexity, whose sub-packetization level is smaller than that of codes in [31]. In addition, by the LU factorization, a decoding method for erasures is obtained. For long codes, the syndromes can be computed fast. When the erased number ρ ≤ 3 (the most common errors in the storage systems), its computational complexity is asymptotically optimal. By an example, the new encoder possesses fewer exclusive ORs per data bit than that of MDS array codes constructed over Rmin [29].

The maximum distance separable (MDS) codes are the optimal codes to achieve Singleton bound, providing maximum error tolerance under a given number of parity nodes. Ye and Barg leveraged permutation matrices and Reed-Solomon type codes to devise 7 explicit constructions for constructing MDS array codes with optimal repair property (as known as MSR codes) or even optimal access property. Drawing inspiration from these explicit constructions, we provide two generic constructions for constructing MSR codes from high-rate MDS codes or MDS array codes. In this paper, we introduce the concepts of s-pairwise MDS codes sets and s-pairwise MDS array codes sets. Two generic constructions (Generic Constructions IandII) for constructing the MSR code using thes-pairwise MDS codes sets or thes-pairwise MDS array codes sets are given. Constructions 1 to 3 proposed by Ye and Barg can be regarded as some special cases ofGeneric Construction I, and Constructions 1 to 3 proposed by Li et al., can be regarded as some special cases ofGeneric Construction II. It is worth mentioning thatGeneric Construction IIcan be applied to any finite field, including the binary field. We also demonstrate how to obtain thes-pairwise MDS code sets and thes-pairwise MDS array code sets from a high-rate MDS code or MDS array code over$\mathbb {F}_{q}$. We obtain a novel class of MSR codes by utilizing the MDS array codes provided by Lv et al., as component codes according toGeneric Construction II. As a byproduct of Constructions 4 to 7, we obtain a new class of MSR codes with optimal access property. Using two types of sets$\Gamma _{1}$and$\Gamma _{2}$with the property that matrices commute, we present several new constructions for MSR codes with the optimal access property over any finite field. In this paper, compared with the constructions over binary field proposed by Li et al., the sub-packetization of our constructions applicable to the binary field is significantly reduced.

It is well-known that erasure codes have been widely applied in the distributed storage systems (DSSs). This paper concentrates on the update bandwidth of erasure codes, which is defined as the system network IO consumption required when a node is updated. Based on the OUB-codes [1] and MDS array codes [2], we introduce the array-OUB-codes which are vertical MDS array codes with triple fault tolerant and minimal update bandwidth. In addition, according to our experiments implemented by C++ program, our array-OUB-codes achieve better encoding and decoding performance compared with OUB-codes. Moreover, through the update bandwidth IO test, our array-OUB-codes can increase the average throughput by 37.5% compared with the RS scheme in [3].

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).

In this short work, a new explicit construction of$q-\mathbf{ary}$MDS array codes with multiple parities will be provided, whose code lengths can be up to$q^{m-1}$, where$m-1$is the size of subpackage. As far as we know, this may be the first explicit construction of practical MDS array codes with such long code lengths for general$q$. In addition, to demonstrate the applicability of our MDS array codes, by the LU factorization of Vandermonde matrices, we present an efficient decoding method aimed at the erased errors, whose computational complexity is$O(m^{2})$in total. Furthermore, if one stores a small number of polynomials in advance or computes the syndrome in a scheduled algorithm, the decoding efficiency of these MDS array codes can be further improved.

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.

EVENODD+ codes are binary maximum distance separable (MDS) array codes for correcting double disk failures in RAID-6 with asymptotically optimal encoding/decoding/update complexities. However, the number of bits stored in each disk of EVENODD+ codes should be an odd number minus one. In this paper, we present a new construction of EVENODD+ codes that have more flexible parameters. The number of bits stored in each disk of our codes is an odd minus one times any positive integer. Moreover, our codes not only have asymptotically optimal encoding/decoding/update complexities but also have lower encoding/decoding/update complexities than the existing EVENODD+ codes.

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.

Cauchy maximum distance separable (MDS) array codes are widely used in storage systems that can support high fault tolerance with systematic form. However, Cauchy MDS array codes suffer from high encoding/decoding complexities and limited parameters. In this paper, we first construct new Cauchy MDS array codes with circulant structure over quotient rings that have flexible sub-packetization. We show that our codes can support more parameters than the existing Cauchy MDS array codes. The sub-packetization of our codes is a multiple of prime minus one, while the sub-packetization of the existing Rabin-Like codes and circulant Cauchy codes is prime minus one. Second, we propose a fast decoding method by designing new division algorithm and employing the LU decomposition of Cauchy matrix for the proposed Cauchy MDS array codes. We show that the decoding complexity of our codes is nearly the same as new Rabin-Like codes [16], and lower than all the other Cauchy MDS array 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}}$.

This paper introduces a privacy-preserving distributed learning framework via private-key homomorphic encryption. Using randomness in the quantization of gradients, our encryption replaces the Gaussian error term of Learning With Errors (LWE) with quantized gradients, thus reducing the error expansion speed in conventional LWE-based homomorphic en-cryption. The proposed system allows a large number of learning participants to engage in distributed learning collaboratively over an honest-but-curious server, while ensuring the cryptographic security of participants' uploaded gradients.

To address the communication bottleneck challenge in distributed learning, our work introduces a novel two-stage quantization strategy designed to enhance the communication efficiency of distributed Stochastic Gradient Descent (SGD). The proposed method initially employs truncation to mitigate the impact of long-tail noise, followed by a non-uniform quantization of the post-truncation gradients based on their statistical characteristics. We provide a comprehensive convergence analysis of the quantized distributed SGD, establishing theoretical guarantees for its performance. Furthermore, by minimizing the convergence error, we derive optimal closed-form solutions for the truncation threshold and non-uniform quantization levels under given communication constraints. Both theoretical insights and extensive experimental evaluations demonstrate that our proposed algorithm outperforms existing quantization schemes, striking a superior balance between communication efficiency and convergence performance.

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.

Distributed storage systems ensure data reliability and availability in the event of a disk failure by employing array codes. Generalized Expanded Blaum-Roth (GEBR) codes and Generalized Expanded Independent Parity(GEIP) codes are MDS array codes with local properties that can tolerate multiple disk failures while maintaining good repair performance. However, when repairing a single-disk failure, the repair bandwidth (defined as the total number of symbols downloaded from other surviving disks in repairing the single-disk failure) is not optimal. To address this issue, we propose a random search algorithm that uses a simulated annealing algorithm to optimize the repair strategy. It starts with a viable repair strategy and gradually replaces the current strategy with another that downloads less data. Experimental results demonstrate that our proposed algorithm can significantly reduce the data required to repair single-disk failure for both GEBR and GEIP codes by 25%-38%, under the selection of suitable parameters, when compared with traditional repair methods. Moreover, our repair algorithm can be done in polynomial time.

With its wide range of applications, the Internet shows a future trend towards abundant and diverse data resources with multiple types of identifiers (multi-identifiers). However, the legacy Domain Name System (DNS) in the current TCP/IP network architecture has failed to manage these identifiers due to the centralized security issue. While some decentralized DNS alternatives have been proposed, they also face scalability issues. In this paper, we propose a blockchain-based Hierarchical Multi-Identifier System, named H-MIS, as a DNS alternative. Specially, it realizes optimal decentralization and scalability by introducing the Zero-Knowledge rollup (ZK-rollup) solution to synchronize the upper and lower on-chain identifier data, as well as off-chain associated resource data. Finally, we implement H-MIS on Ethereum and evaluate its performance. The experimental results indicate that compared to the original MIS and Ethereum Name Service (ENS), H-MIS has advantages in such aspects as efficiency, data consumption, and Gas fees.

Reed-Solomon (RS) codes are widely used in storage systems to provide high data reliability. The existing RS codes are constructed over finite field with field size larger than the code length that have high encoding/decoding complexity. In this paper, we propose a new construction for RS codes over a cyclic ring instead of finite field. Our new RS codes only incurs XOR and cyclic-shift operation in the encoding/decoding processes, and therefore have lower encoding/decoding complexity than the existing RS codes. In addition, we show that we can employ the efficient Reed-Muller (RM) transform in our new RS codes that reduces the encoding/decoding complexity. Moreover, we implement our new RS codes by C++ and show that our new RS codes have better encoding/decoding performance than the existing RS codes for the evaluated parameters.

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.

EVENODD code is a binary maximum distance separable (MDS) array code with two parity columns, where the number of bits in each column should be a prime number minus one. In this paper, we present the EVENODD* codes that can support much more parameters, i.e., the number of bits in each column is not only a prime number minus one, but also other positive integers. EVENODD code can be viewed as a special case of our EVENODD* codes. Moreover, we present the decoding methods for any two-column erasures of the EVENODD* codes and show that the decoding complexity of the EVENODD* codes is almost the same as that of EVENODD codes.

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.

Based on the Reed-Muller (RM) transform, this paper proposes a Reed-Solomon (RS) encoding/erasure decoding algorithm for any number of parities. Specifically, we first generalize the previous RM-based syndrome calculation, which allows only up to seven parities, to support any number of parities. Then we propose a general encoding/erasure decoding algorithm. The proposed encoding algorithm eliminates the operations in solving linear equations, and this improves the computational efficiency of existing RM-based RS algorithms. In terms of erasure decoding, this paper employs the generalized RM-based syndrome calculation and lower–upper (LU) decomposition to accelerate the computational efficiency. Analysis shows that the proposed encoding/erasure decoding algorithm approaches the complexity of$\lfloor \lg T \rfloor + 1$XORs per data bit with$N$increasing, where$T$and$N$denote the number of parities and codeword length respectively. To highlight the advantage of the proposed RM-based algorithms, the implementations with Single Instruction Multiple Data (SIMD) technology are provided. Simulation results show that the proposed algorithms are competitive, as compared with other cutting-edge implementations.

The increasing capacity of storage devices and the growing frequency of correlated failures demands better fault tolerance by using maximum distance separable (MDS) array codes with triple-parity. Although many constructions of triple-parity MDS array codes have been proposed, they either have large update complexity or have large encoding/decoding complexity or only support specified parameters. In this paper, we propose two classes of triple-parity MDS array codes, called extended EVENODD+ and STAR+ that both have asymptotically optimal update complexity and lower encoding/decoding complexity. We show that the existing extended EVENODD and STAR are a special case of our extended EVENODD+ and STAR+, respectively. Moreover, we show that our extended EVENODD+ and STAR+ have strictly less encoding/decoding/update complexity than that of extended EVENODD and STAR for most parameters.

An$(n,k)$recoverable property array code is composed of$m\times n$arrays such that any$k$out of$n$columns suffice to retrieve all the information symbols, where$n > k$. Note that maximum distance separable (MDS) array code is a special$(n,k)$recoverable property array code of size$m\times n$with the number of information symbols being$km$. Expanded-Blaum-Roth (EBR) codes and Expanded-Independent-Parity (EIP) codes are two classes of$(n,k)$recoverable property array codes that can repair any one symbol in a column by locally accessing some other symbols within the column, where the number of symbols$m$in a column is a prime number. By generalizing the constructions of EBR and EIP codes, we propose new$(n,k)$recoverable property array codes, such that any one symbol can be locally recovered and the number of symbols in a column can be not only a prime number but also a power of an odd prime number. Also, we present an efficient encoding/decoding method for the proposed generalized EBR (GEBR) and generalized EIP (GEIP) codes based on the LU factorization of a Vandermonde matrix. We show that the proposed decoding method has less computational complexity than existing methods. Furthermore, we show that the proposed GEBR codes have both a larger minimum symbol distance and a larger recovery ability of erased lines for some parameters when compared to EBR codes. We also present a necessary and sufficient condition of enabling EBR codes to recover any$r$erased lines of a slope for any parameter$r$, which was an open problem. Moreover, we show that EBR codes can recover any$r$consecutive erased lines of any slope for any parameter$r$.

Partial maximum distance separable (PMDS) codes are a kind of erasure codes where the nodes are divided into multiple groups with each forming an MDS code with a smaller code length, thus they allow repairing a failed node with only a few helper nodes and can correct all erasure patterns that are information-theoretically correctable. However, the repair of a failed node of PMDS codes still requires a large amount of communication if the group size is large. Recently, PMDS array codes with each local code being an MSR code were introduced to reduce the repair bandwidth further. However, they require extensive rebuilding access and unavoidably a significant sub-packetization level. In this paper, we first propose two constructions of PMDS array codes with two global parities that have smaller sub-packetization levels and much smaller finite fields than the existing one. One construction can support an arbitrary number of local parities and has$(1+\epsilon)$-optimal repair bandwidth (i.e.,$(1+\epsilon)$times the optimal repair bandwidth), while the other one is limited to two local parities but has significantly smaller rebuilding access and its sub-packetization level is only 2. In addition, we present a construction of PMDS array code with three global parities, which has a smaller sub-packetization level as well as$(1+\epsilon)$-optimal repair bandwidth, the required finite field is significantly smaller than existing ones.

A locally repairable code (LRC) is a linear code that each code symbol can be encoded by downloading a small number (at most r) of other code symbols. In this paper, we use the parity-check matrix approach to obtain 58 classes code parameters for octonion-field optimal LRCs of distance 3. Then three optimal oction-field LRCs of distance 4 with locality r = 2 and r = 3 are given by adding linear independent set to the parity-check matrix.

Improving the repair performance of erasure code is a critical issue in order to maintain high data reliability in modern large-scale storage systems. Locally repairable codes (LRC) can improve the repair performance by locally repairing any single-node failure. In modern distributed cluster storage systems, the cross-cluster bandwidth is more scarce than the innercluster bandwidth. In this paper, we propose a well-designed placement strategy for LRC which is suitable for storing hot data. We show that our proposed placement strategy can reduce the cross-cluster bandwidth overhead in repairing node failures. Compared with the flat placement, the cross-cluster repair bandwidth can be reduced by more than 91.7% with our placement strategy in repairing one single-node failure, while the cross-cluster repair bandwidth reduction is 90.8% in repairing two-node failures.

A (k+2,k,m) maximum distance separable (MDS) array code is an array of size m × (k + 2) such that any k out of k +2 columns can retrieve all km information bits. The (k + 2,k,m) array code can correct a single criss-cross error means that the code can retrieve all km information bits if any single column or row is in error. In this paper, we propose new systematic (k + 2,k,m) MDS array codes that can correct a single criss-cross error. In addition, we present efficient decoding algorithms that has lower decoding complexity for any two-row erasures or two-column erasures or one-row plus one-column erasures or one-row error or one-column error. Moreover, we show that our codes have much lower update complexity than that of the existing MDS array codes correcting a single criss-cross error [1].

Large-scale high code-rate maximum distance separable (MDS) codes are critical and important in distributed storage systems that can provide high fault tolerance with extremely small storage redundancy. Repair access (defined as the total amount of symbols accessed in repairing one single-node failure) is a key metric of designing MDS codes. In large-scale MDS codes, one single-node failure can be recovered by connecting a large number of helper nodes. However, one or more helper nodes may be busy and can not send symbols during the repair process. In this paper, we define the total amount of symbols accessed in repairing one single-node failure with one or more busy nodes as the repair access with busy-node. We then propose a class of MDS array codes over a well-designed binary cyclic ring that is with small sub-packetization, small repair access, small repair access with busy-node, and small encoding complexity.

Partial maximum distance separable (PMDS) codes are a kind of erasure codes where the storage nodes are divided into multiple groups with each forming an MDS code of a smaller code length. They allow repairing a failed node by contacting only a few helper nodes and can correct all erasure patterns which are information-theoretically correctable. However, the repair of a failed node of PMDS codes still requires a large amount of communication if the group size is large. Recently, PMDS array codes with each local code being an MSR code were introduced to further reduce the repair bandwidth, but codes over small finite fields only exist for two global parities, and require large rebuilding access and unavoidably a large sub-packetization level. In this paper, we propose two constructions of PMDS array codes with two and three global parities, respectively. Both have a small sub-packetization level, small repair bandwidth, and much smaller finite fields than existing ones.

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.

In data centers, storage nodes are organized in racks and the cross-rack communication bandwidth is often much lower than the intra-rack communication bandwidth. Two common failures in data centers are single-node failures and single-rack failures. In this paper, we study the problem of minimizing the cross-rack repair bandwidth in both repairing single-node failures and repairing single-rack failures. We characterize, given that the minimum cross-rack repair bandwidth for single-node failures is achieved, the optimal trade-off between storage and cross-rack repair bandwidth for single-rack failures. We further propose a general family of storage codes, Generalized Rack-aware Regenerating Codes (GRRC), that achieve the optimal trade-off. We obtain two extreme points of GRRC, namely the minimum storage generalized rack-aware regeneration (MSGRR) point and the minimum bandwidth generalized rack-aware regeneration (MB-GRR) point. We show that MSGRR codes have strictly less cross-rack repair bandwidth for single-rack failures than the related minimum storage multi-node repair codes for most parameters. We also show that MBGRR codes have less cross-rack repair bandwidth for single-rack failures than the minimum bandwidth multi-node repair codes for all our evaluated parameters.

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$.

STAR codes are well-known binary Maximum Distance Separable (MDS) array codes with triple fault tolerance and low encoding/decoding complexity, yet the update complexity of STAR codes is sub-optimal. We propose STAR+ codes, which extend STAR codes to achieve asymptotically optimal update complexity. We show that STAR+ codes are the generalized version of STAR codes with triple fault tolerance, and additionally have strictly less complexity in encoding, decoding, and updates than STAR codes for most parameters.

In this paper, we consider two rack-aware storage systems. First, large-scale rack-aware storage system, which is very common in large-scale storage system, is a rack-aware storage system where all sizes of racks are at least the number of redundant nodes. For such storage system, we prove that any Maximum Distance Separable (MDS) codes can have optimal inter-rack repair bandwidth and give a closed-form representation of all repair schemes with optimal inter-rack repair bandwidth. Furthermore, we show that the optimal repair access and optimal inter-rack repair bandwidth can be attained simultaneously for such storage system. Second, we investigate the rack-aware storage system of all racks with the same size, which is called uniform rack-aware storage system. We prove that, except the trivial cases, we cannot attain optimal inter-rack repair bandwidth and optimal repair access for such storage system at the same time. Specifically, we establish the lower bound of repair access for a repair scheme with optimal interrack repair bandwidth, which is tight for some parameters, and also the tight lower bound of inter-rack repair bandwidth for a repair scheme with optimal repair access.

In this paper, we consider the update bandwidth in distributed storage systems (DSSs). The update bandwidth, which measures the transmission efficiency of the update process in DSSs, is defined as the average amount of data symbols transferred in the network when the data symbols stored in a node are updated. This paper contains the following contributions. First, we establish the closed-form expression of the minimum update bandwidth attainable by irregular array codes. Second, after defining a class of irregular array codes, called Minimum Update Bandwidth (MUB) codes, which achieve the minimum update bandwidth of irregular array codes, we determine the smallest code redundancy attainable by MUB codes. Third, the code parameters, with which the minimum code redundancy of irregular array codes and the smallest code redundancy of MUB codes can be equal, are identified, which allows us to define MR-MUB codes as a class of irregular array codes that simultaneously achieve the minimum code redundancy and the minimum update bandwidth. Fourth, we introduce explicit code constructions of MR-MUB codes and MUB codes with the smallest code redundancy. Fifth, we establish a lower bound of the update complexity of MR-MUB codes, which can be used to prove that the minimum update complexity of irregular array codes may not be achieved by MR-MUB codes. Last, we construct a class of$(n = k + 2, k)$vertical maximum-distance separable (MDS) array codes that can achieve all of the minimum code redundancy, the minimum update bandwidth and the optimal repair bandwidth of irregular array codes.

Expanded-Blaum-Roth (EBR) code encodes a (p - 1) × k information array into a p × p array such that any bit in a column can be recovered within the column and any k out of p columns can retrieve all (p - 1) × k information bits, where p is a prime number. In this paper, we generalize the construction of EBR code with a more flexible parameter, i.e., the number of bits stored in a column in the proposed construction can be not only a prime number but also an even number. In addition, we present an efficient encoding/decoding method for the proposed generalized EBR codes based on the LU factorization of Vandermonde matrix. We show that the proposed encoding/decoding method has less computational complexity than the existing method. Moreover, we show that the minimum symbol distance of generalized EBR codes is the same as that of EBR code for some parameters.

Modern data centers often organize storage nodes in racks, in which the cross-rack communication cost is typically much higher than the intra-rack communication cost. Rack-aware regenerating codes have recently been proposed to achieve the optimal trade-off between storage redundancy and cross-rack repair bandwidth, subject to the condition that the original data can be reconstructed from a sufficient number of any non-failed nodes. In this paper, we present a coding framework that transforms any minimum-storage regenerating (MSR) code to a minimum-storage rack-aware regenerating (MSRR) code, such that the cross-rack repair bandwidth is minimized subject to the minimum storage redundancy. To this end, we can construct a family of exact-repair constructions for the MSRR codes for all admissible parameters. Furthermore, our constructions achieve low sub-packetization, which is critical for mitigating the I/O overhead during repair.

An (n, k) maximum distance separable (MDS) code encodes kα data symbols into nα symbols that are stored in n nodes with α symbols each, such that the kα data symbols can be reconstructed from any k out of n nodes. MDS codes achieve optimal repair access if we can repair the lost symbols of any single node by accessing α/[d - k + 1] symbols from each of d other surviving nodes, where k + 1 ≤ d ≤ n - 1. In this paper, we propose a generic transformation for any MDS code to achieve optimal repair access for a single-node repair among d - k + 1 nodes, while the transformed MDS codes maintain the same update bandwidth (i.e., the total amount of symbols transferred for updating the symbols of affected nodes when some data symbols are updated) as that of the underlying MDS codes. By recursively applying our transformation for existing MDS codes with the minimum update bandwidth, we can obtain multi-layer transformed MDS codes that achieve both optimal repair access for any single-node repair among all n nodes and minimum update bandwidth.

A novel implementation of a special class of Galois ring, in which the multiplication can be realized by a cyclic convolution, is applied to the construction of network codes. The primitive operations involved are byte-wise shifts and integer additions modulo a power of 2. Both of them can be executed efficiently in microprocessors. An illustration of how to apply this idea to array code is given at the end of the paper.

An mx(k+r) binary maximum distance separable (MDS) array code contains k information columns and r parity columns with each entry being a bit, where any k out of k + r columns can recover the k information columns. When there is a failed column, it is critical to minimize the repair bandwidth that is the total number of bits downloaded from d out of k + r - 1 surviving columns in repairing the failed column. In this article, we first propose two explicit constructions of binary MDS array codes that have asymptotically optimal repair bandwidth for any information column, where r ≥ 2 and d = k + r - 1 for the first construction, and r ≥ 4 is an even number and d = k + r/2 - 1 for the second construction. By applying a generic transformation for the proposed two classes of binary MDS array codes, we then obtain two classes of new binary MDS array codes that also have optimal repair bandwidth for any parity column and asymptotically optimal repair bandwidth for any information column.

Zigzag-decodable codes have been proposed for distributed storage systems to achieve fast decoding of uncoded data packets through the iterative decoding of data bits from coded packets. To maintain high data availability, it is critical to minimize the repair bandwidth by downloading the least amount of bits for repairing any lost packet. In this work, we propose zigzag-decodable reconstruction (ZDR) codes which achieve asymptotically minimum repair bandwidth for repairing a single node, while preserving the high computational efficiency due to zigzag decoding. We present two explicit constructions of ZDR codes such that any node of ZDR codes can be repaired with asymptotically minimum repair bandwidth. The first construction is based on the well-designed encoding matrix and a generic transformation, while the second construction is designed by recursively employing the proposed generic transformation for any existing zigzag-decodable code. Moreover, we show that the proposed two classes of ZDR codes can be decoded by the zigzag decoding algorithm and have less computational complexity than the existing codes with asymptotically or exactly minimum repair bandwidth.

Consider a binary maximum distance separable (MDS) array code composed of an m x (k + r) array of bits with k information columns and r parity columns, such that any k out of k + r columns suffice to reconstruct the k information columns. Our goal is to provide optimal repair access for binary MDS array codes, meaning that the bandwidth triggered to repair any single failed information or parity column is minimized. In this paper, we propose a generic transformation framework for binary MDS array codes, using EVENODD codes as a motivating example, to support optimal repair access for k + 1 ≤ d ≤ k + r - 1, where d denotes the number of nonfailed columns that are connected for repair; note that when d <; k + r - 1, some of the chosen d columns in repairing a failed column are specific. In addition, we show how our transformation framework applies to an example of binary MDS array codes with asymptotically optimal repair access of any single information column and enables asymptotically or exactly optimal repair access for any column. Furthermore, we present a new transformation for EVENODD codes with two parity columns such that the existing efficient repair property of any information column is preserved and the repair access of parity column is optimal.

An m x (k+r) binary maximum distance separable (MDS) array code contains k information columns and r parity columns with each entry being a bit such that any k out of k+r columns can retrieve the k information columns. When there is a failed column, it is critical to minimize the repair bandwidth that is the total number of bits downloaded from d out of k+r-1 surviving columns in repairing the failed column. In this paper, we first propose a new construction of binary MDS array codes with any number of parity columns (i.e., r≥2) that have asymptotically optimal repair bandwidth for any information column, where d=k+r-1. By applying a transformation for the proposed binary MDS array codes, we then can obtain the transformed binary MDS array codes that also have optimal repair bandwidth for any parity column.

Regenerating code is a class of erasure codes designed for distributed storage systems that can achieve optimal tradeoff between storage and repair bandwidth. Most existing constructions of regenerating codes are based on a finite field with large enough size. Recently, a new construction of regenerating codes over a binary cyclic code was proposed. It was shown that the new construction has lower computational complexity than the construction based on finite fields. This paper generalizes the construction by designing regenerating codes with binary cyclic codes that support more parameters. We show that the proposed coding method can achieve the fundamental tradeoff curve between the storage and repair bandwidth. We also give an example that an existing construction of regenerating codes can be transformed to a regenerating code over a binary cyclic code with less computational complexity. Furthermore, the proposed coding framework has more design space for exact repair constructions of minimum storage regenerating codes.

BACKGROUND: Collective cell migration is a significant and complex phenomenon that affects many basic biological processes. The coordination between leader cell and follower cell affects the rate of collective cell migration. However, there are still very few papers on the impacts of the stimulus signal released by the leader on the follower. Tracking cell movement using 3D time-lapse microscopy images provides an unprecedented opportunity to systematically study and analyze collective cell migration. RESULTS: Recently, deep reinforcement learning algorithms have become very popular. In our paper, we also use this method to train the number of cells and control signals. By experimenting with single-follower cell and multi-follower cells, it is concluded that the number of stimulation signals is proportional to the rate of collective movement of the cells. Such research provides a more diverse approach and approach to studying biological problems. CONCLUSION: Traditional research methods are always based on real-life scenarios, but as the number of cells grows exponentially, the research process is too time consuming. Agent-based modeling is a robust framework that approximates cells to isotropic, elastic, and sticky objects. In this paper, an agent-based modeling framework is used to establish a simulation platform for simulating collective cell migration. The goal of the platform is to build a biomimetic environment to demonstrate the importance of stimuli between the leading and following cells.

Binary maximum distance separable (MDS) array codes are a special class of erasure codes for distributed storage that not only provides fault tolerance with minimum storage redundancy but also achieves low computational complexity. They are constructed by encoding k information columns into r parity columns, in which each element in a column is a bit, such that any k out of the k + r columns suffice to recover all information bits. In addition to providing fault tolerance, it is critical to improve repair performance in practical applications. Specifically, if a single column fails, then our goal is to minimize the repair bandwidth by downloading the least amount of bits from d healthy columns, where k <; d <; k + r - 1. If one column of an MDS code is failed, it is known that we need to download at least 1/(d - k + 1) fraction of the data stored in each of the d healthy columns. If this lower bound is achieved for the repair of the failure column from accessing arbitrary d healthy columns, we say that the MDS code has optimal repair. However, if such lower bound is only achieved by d specific healthy columns, then we say the MDS code has weak-optimal repair. In this paper, we propose two explicit constructions of binary MDS array codes with more parity columns (i.e., r ≥ 3) that achieve asymptotically weak-optimal repair, where k + 1 <; d <; k + L(r - 1)/2J, and “asymptotic" means that the repair bandwidth achieves the minimum value asymptotically in d. Codes in the first construction have odd number of parity columns and asymptotically weak-optimal repair for anyone information failure, while codes in the second construction have even number of parity columns and asymptotically weak-optimal repair for any one column failure.

Erasure coding is widely used for massive storage in data centers to achieve high fault tolerance and low storage redundancy. Since the cross-rack communication cost is often high, it is critical to design erasure codes that minimize the cross-rack repair bandwidth during failure repair. In this paper, we analyze the optimal trade-off between storage redundancy and cross-rack repair bandwidth specifically for data centers, subject to the condition that the original data can be reconstructed from a sufficient number of any non-failed nodes. We characterize the optimal trade-off curve under functional repair, and propose a general family of erasure codes called rack-aware regenerating codes (RRC), which achieve the optimal trade-off. We further propose exact repair constructions of RRC that have minimum storage redundancy and minimum cross-rack repair bandwidth, respectively. We show that (i) the minimum storage redundancy constructions support a wide range of parameters and have cross-rack repair bandwidth that is strictly less than that of the classical minimum storage regenerating codes in most cases, and (ii) the minimum cross-rack repair bandwidth constructions support all the parameters and have less cross-rack repair bandwidth than that of the minimum bandwidth regenerating codes for almost all of the parameters.

BACKGROUND: The cooperation of cells in biological systems is similar to that of agents in cooperative multi-agent systems. Research findings in multi-agent systems literature can provide valuable inspirations to biological research. The well-coordinated states in cell systems can be viewed as desirable social norms in cooperative multi-agent systems. One important research question is how a norm can rapidly emerge with limited communication resources. RESULTS: In this work, we propose a learning approach which can trade off the agents' performance of coordinating on a consistent norm and the communication cost involved. During the learning process, the agents can dynamically adjust their coordination set according to their own observations and pick out the most crucial agents to coordinate with. In this way, our method significantly reduces the coordination dependence among agents. CONCLUSION: The experiment results show that our method can efficiently facilitate the social norm emergence among agents, and also scale well to large-scale populations.

In this paper, we study the delay-constrained input-queued switch, where each packet has a deadline and it will expire if it is not delivered before its deadline. Such new scenario is motivated by the proliferation of real-time applications in multimedia communication systems, tactile Internet, networked controlled systems, and cyber-physical systems. The delay-constrained input-queued switch is completely different from the well-understood delay-unconstrained one and thus poses new challenges. We focus on three fundamental problems centering around the performance metric of timely throughput: (i) how to characterize the capacity region? (ii) how to design a feasibility/throughput-optimal scheduling policy? and (iii) how to design a network-utility-maximization scheduling policy? We use three different approaches to solve these three fundamental problems. The first approach is based on Markov Decision Process (MDP) theory, which can solve all three problems. However, it suffers from the curse of dimensionality. The second approach breaks the curse of dimensionality by exploiting the combinatorial features of the problem. It gives a new capacity region characterization with only a polynomial number of linear constraints. The third approach is based on the framework of Lyapunov optimization, where we design a polynomial-time maximum-weight $T$ -disjoint-matching scheduling policy which is proved to be feasibility/throughput-optimal. Our three approaches apply to the frame-synchronized traffic pattern but our MDP-based approach can be extended to more general traffic patterns.

Array codes have been widely used in communication and storage systems. To reduce computational complexity, one important property of the array codes is that only exclusive OR operations are used in the encoding and decoding processes. Cauchy Reed-Solomon codes, Rabin-like codes, and circulant Cauchy codes are existing Cauchy maximum-distance separable (MDS) array codes that employ Cauchy matrices over finite fields, circular permutation matrices, and circulant Cauchy matrices, respectively. All these codes can correct any number of failures; however, a critical drawback of existing codes is the high decoding complexity. In this paper, we propose a new construction of Rabin-like codes based on a quotient ring with a cyclic structure. The newly constructed Rabin-like codes have more supported parameters (prime p is extended to an odd number), such that the world sizes of them are more flexible than the existing Cauchy MDS array codes. An efficient decoding method using LU factorization of the Cauchy matrix can be applied to the newly constructed Rabin-like codes. It is shown that the decoding complexity of the proposed approach is less than that of existing Cauchy MDS array codes. Hence, the Rabin-like codes based on the new construction are attractive to distributed storage systems.

Array codes are used widely in data storage systems such as redundant array of independent disks. The row-diagonal parity (RDP) codes and EVENODD codes are two popular double-parity array codes. The increasing capacity of hard disks demands better fault tolerance by using array codes with three or more parity disks. Although many extensions of RDP and EVENODD codes have been proposed, their main drawback is high decoding complexity. In this paper, we propose a unified form of RDP and EVENODD codes under which RDP codes can be treated as shortened EVENODD codes. Moreover, an efficient decoding algorithm based on an LU factorization of a Vandermonde matrix is proposed. The LU decoding method is applicable to all the erasure patterns of RDP and EVENODD codes with three parity columns. It is also applicable to the erasure decoding of RDP and EVENODD codes with more than three parity columns when the number of continuous surviving parity columns is no less than the number of erased information columns and the first parity column has not failed. The proposed efficient decoding algorithm is also applicable to other Vandermonde array codes, with less decoding complexity than that of the existing method.

As the Internet and the big data system evolve rapidly, the deployment of distributed applications becomes widespread, promoting the development of Distributed File System (DFS). The existing defense technologies for DFS, such as detection or patching, mainly aim to protect the system from known attacks and vulnerabilities. However, it is difficult for those systems to solve the growing security issues from the unknown threats due to their passiveness and hysteresis. In this paper, we propose MDFS, a mimic defense theory based architecture for DFS with the capability to improve the data security. Mimic Defense (MD), a proactive defense embedded in MDFS, emphasizes dynamism, heterogeneity and redundancy. The key benefits of MD are transferring the attack surface as well as increasing the cost of modification.

Ceph is a reliable, scalable, unified distributed storage system, and recently has become one of OpenStack's standard open source storage solutions. For the reason of the low performance, Ceph Filesystem (Cephfs) cannot employ erasure codes directly, especially for binary Reed-Solomon (BRS) codes, whose size of the parity block is larger than that of the data block. To address these problems, we implemented efficient BRS codes, and filled the gap between BRS codes and Cephfs by a simple conversion. In addition to that, an efficient framework consisting of filesystem, cache tier and storage tier was adopted in Ceph to ensure that the file data is finally stored with the erasure coding technology. The experimental results show that such a design spends a small amount of additional cost but obtains much better effects.

Distributed storage systems are composed by many unreliable storage nodes over a network. A data file is redundantly stored in multiple storage nodes to provide high reliability. Recently erasure codes with Maximum Distance Separable (MDS) property are gradually employed in distributed storage systems to reduce the cost of reliably storing large amounts of data. Regenerating codes are a class of erasure codes which can achieve the optimal trade-off between the storage capacity and the bandwidth needed to repair a failed node. However, one of the critical drawbacks of existing MDS erasure codes in general is the high coding and repair complexities, since the coding and repair processes involve expensive multiplication operations in a finite field. Binary Addition and Shift Implementable Cyclic-convolutional (BASIC) codes, which is a coding framework of linear codes with a binary cyclic code as the alphabet, were proposed recently with lower computational complexity by replacing a finite field multiplication by a cyclic-shift operation. This paper provides an overview of the existing results of BASIC codes, and proposes several interesting open problems about BASIC codes.

Binary maximum distance separable (MDS) array codes are a special class of erasure codes for distributed storage that not only provide fault tolerance with minimum storage redundancy, but also achieve low computational complexity. They are constructed by encoding k information columns into r parity columns, in which each element in a column is a bit, such that any k out of the k + r columns suffice to recover all information bits. In addition to providing fault tolerance, it is critical to improve repair performance. Specifically, if a single column fails, our goal is to minimize the repair bandwidth by downloading the least amount of bits from d non-failed columns, where k ≤ d ≤ k + r − 1. However, existing binary MDS codes that achieve high data rates (i.e., k/(k + r) > 1/2) and minimum repair bandwidth only support double fault tolerance (i.e., r = 2), which is insufficient for failure-prone distributed storage environments in practice. This paper fills the void by proposing an explicit construction of triple-fault-tolerant (i.e., r = 3) binary MDS array codes that achieve asymptotically minimum repair bandwidth for d = k + 1.

To reduce multiple‐failure repair traffic in erasure coded storage systems, Patrick Lee et al. introduce concurrent framework‐based minimal‐storage regenerating codes (RGCs). The approach is simpler and more practical than the cooperative mechanism in non‐fully distributed environment. This study unifies such class of codes as concurrent RGC and further studies the characteristics by analysing the cut‐based information flow graph. The authors present a general storage–bandwidth tradeoff and give closed‐form expressions for the points on the curve including the minimal‐bandwidth point. They show that the concurrent RGC can be constructed by reforming the existing single‐node RGC or multiple‐node cooperative RGC. Moreover, a connection to strong‐maximum distance separable is also analysed.

Measurement traces from real-world production environment show that the execution time of tasks within a MapReduce job varies widely due to the variability in machine service capacity. This variability issue makes efficient job scheduling over large-scale MapReduce clusters extremely challenging. To tackle this problem, we adopt the task cloning approach to mitigate the effect of machine variability and design corresponding scheduling algorithms so as to minimize the overall job flowtime in different scenarios. For offline scheduling where all jobs arrive at the same time, we design an$O(1)$-competitive algorithm, which gives priorities to jobs with small effective workload. We then extend this offline algorithm to yield the so-called Smallest Remaining Effective Workload based$\beta$-fraction Sharing plus Cloning algorithm (SREW+C($\beta$)) for the online case. We also show that SREW+C($\beta$) is$(1+ 2\beta + \epsilon)$-speed$O(\frac{1}{\beta \epsilon })$-competitive with respect to the sum of job flowtime within a cluster. We demonstrate via trace-driven simulations that SREW+C($\beta$) can significantly reduce the overall job flowtime by cutting down the elapsed time of small jobs substantially. In particular, SREW+C($\beta$) reduces the total job flowtime by 14, 10 and 11 percent respectively when comparing to Mantri, Dolly and Grass.

In distributed storage systems, regenerating codes can achieve the optimal tradeoff between storage capacity and repair bandwidth. However, a critical drawback of existing regenerating codes, in general, is the high coding and repair complexity, since the coding and repair processes involve expensive multiplication operations in finite field. In this paper, we present a design framework of regenerating codes, which employ binary addition and bitwise cyclic shift as the elemental operations, named BASIC regenerating codes. The proposed BASIC regenerating codes can be regarded as a concatenated code with the outer code being a binary parity-check code, and the inner code being a regenerating code utilizing the binary parity-check code as the alphabet. We show that the proposed functional-repair BASIC regenerating codes can achieve the fundamental tradeoff curve between the storage and repair bandwidth asymptotically of functional-repair regenerating codes with less computational complexity. Furthermore, we demonstrate that the existing exact-repair product-matrix construction of regenerating codes can be modified to exact-repair BASIC product-matrix regenerating codes with much less encoding, repair, and decoding complexity from the theoretical analysis, and with less encoding time, repair time, and decoding time from the implementation results.

Distributed file system has emerged in recent years as an efficient solution to store the large amount of data produced anytime and anywhere. In order to guarantee data reliability, it is necessary to introduce redundancy to the storage systems. Compared to simple replication, practical systems are increasingly adopting erasure codes for better storage efficiency. However, traditional erasure codes such as maximum-distance-separable (MDS) codes, are designed over a large finite field, which inevitably hinders the wide implementation of erasure codes. In this paper, we propose a new family of MDS codes with high computation efficiency. More specifically, only XOR operation is included in the encoding process to generate parity blocks. Upon failure of a storage node, we use the efficient Zigzag decoding method to recover the failed blocks, which achieves the optimal encoding and an efficient decoding. Furthermore, we implement the proposed codes in a distributed file system, and the results show the high performance of the new codes.

Recently, traditional erasure codes such as Reed-Solomon (RS) codes have been increasingly deployed in many distributed storage systems to reduce the large storage overhead incurred by the widely adopted replication scheme. However, these codes require significantly high resources with respect to network bandwidth and disk I/O during recovery of missing or unavailable data. It is referred as the recovery problem. In this paper, we dedicate to integrating exact minimum bandwidth regenerating codes into practical systems to solve the recovery problem. We design an implementation friendly storage code with the recently proposed BASIC framework and ZigZag decodable code for saving recovery bandwidth and disk I/O. We build a system called STORE based on this code and evaluate our prototype atop a HDFS cluster testbed with 21 nodes. As shown in this paper, the recovery bandwidth achieves minimum approximately during recovery of both data block and parity block with STORE. Another attractive result is that the recovery disk I/O also achieves minimum approximately during recovery of data block. Due to the reduction of recovery bandwidth and disk I/O, the degraded read throughput is boosted notably.

We present a new family of maximal-distance separable (MDS) array codes which can tolerate five disk failures. The encoding is based on bit-wise exclusive OR (XOR) and bit-wise cyclic shifts, and hence is amenable to practical implementation. Efficient repair method for correcting up to two disk failures is also given. The proposed coding scheme provides a larger spectrum of parameters, with comparable encoding and repairing complexities in compare with existing MDS array codes, such as the row-diagonal parity (RDP) code and the EVENODD code.

We present a design framework of regenerating codes for distributed storage systems which employ binary additions and bit-wise cyclic shifts as the basic operations. The proposed coding method can be regarded as a concatenation coding scheme with the outer code being a binary cyclic code, and the inner code a regenerating code utilizing the binary cyclic code as the alphabet set. The advantage of this approach is that encoding and repair of failed node can be done with low computational complexity. It is proved that the proposed coding method can achieve the fundamental tradeoff curve between the storage and repair bandwidth asymptotically when the size of the data file is large.

Regenerating codes (RGC) are a class of distributed storage codes that can provide efficient repair of failure nodes in distributed storage systems. In general, the reduction of repair bandwidth of RGC is at the expense of a small increase in storage cost and computational cost. The high computational complexity of data coding over a finite field of large size makes it unsuitable for practical distributed storage systems. BASIC codes, which stands for Binary Addition and Shift Implementable Convolutional codes, is introduced in [1] with the aim of reducing computational complexity, while retaining the benefits of RGC. In this paper, we present a construction of exact-repair BASIC codes at the minimum-storage point (MSR). A helper node needs no coding to repair a failure node for the minimum-storage BASIC codes. The results of simulation show minimum-storage BASIC codes outperform Cauchy Reed-Solomon codes in both repairing cost and coding cost.

The explosion of big data stored in distributed file systems calls for more efficient storage paradigms. While replication is widely used to ensure data availability, erasure codes provide a much better tradeoff between storage and availability. Reed-Solomon (RS) codes are the standard design choice, however, their high repair cost is often considered an unavoidable price to pay for high storage efficiency and high reliability. BASIC codes can achieve the optimal tradeoff between storage capacity and repair bandwidth with much less complexity of regenerating codes, which is first proposed in [1]. This paper integrate one construction of the minimum storage BASIC (MS-BASIC) codes [2] into a Hadoop HDFS cluster testbed with up to 22 storage nodes. We demonstrate that MS-BASIC codes conform to the theoretical findings and achieve recovery bandwidth saving compared to the conventional recovery approach based on RS codes.

In distributed storage systems, a data file is encoded and distributed to storage nodes, such that the data file can be recovered from some subsets of the nodes. Upon the failure of a storage node, we want to repair it efficiently by contacting and downloading some encoded bits from a small number of surviving nodes. Using projective-geometric self-repairing codes (PSRC), proposed by Oggier and Datta, one can repair a failed node by contacting only two nodes. However, in their construction, the number of storage nodes in the storage system is a large number, and thus the storage efficiency is low. In this paper, we investigate how to be more flexible in the number of storage nodes. The proposed code in this paper is called general projective geometric self-repairing codes (GPSRC). GPSRC reduces high redundancy of PSRC, while retains the basic property of PSRC. We present some methods for repairing a failed node, in which the number of contacted surviving nodes is flexible. These repairing methods provide tradeoff between repair-degree and repair-bandwidth.

Regenerating code is a class of storage codes that achieve the optimal trade-off between storage capacity and repair bandwidth, which are two important performance metrics in data storage systems. However, existing constructions of regenerating codes rely on expensive computational operations such as finite field multiplication. The high coding and repair complexity limit their applications in large-scale practical storage systems. In this paper, we show that it is possible to achieve the full potential of regenerating codes with low computational complexity. In particular, we propose a new class of regenerating codes, called BASIC codes, that can achieve two specific points (i.e., minimum-bandwidth and minimum-storage regenerating points) on the storage and repair bandwidth trade-off curve, using only binary addition and shift operations in the coding and repair processes. Although in this paper we focus on constructing and analyzing BASIC codes for two specific exact-repair settings, our framework can be generalized to develop BASIC codes for more general exact- and functional-repair regenerating codes.