Maximum distance separable (MDS) codes in distributed storage systems provide the optimal tradeoff between fault tolerance and storage overhead. As a kind of MDS codes, minimum storage regenerating (MSR) codes have attracted a lot of attention since they are also optimal in terms of repair bandwidth. However, MSR codes suffer from a high repair degree, meaning many helper nodes are needed in the node repair process. Compared to MSR codes, locally repairable codes (LRCs) can significantly reduce the repair degree at the cost of increased storage overhead. The recently introduced concept of vector LRCs combines the advantages of MSR codes and LRCs, providing a tradeoff between repair degree/repair bandwidth and storage overhead. Most existing vector LRCs are built on MSR codes or their shortened versions. However, existing MSR codes have an unavoidably large sub-packetization levels, which also result in large sub-packetization levels in the corresponding vector LRCs. In this paper, we propose a new vector LRC structure, where MDS array codes (without shortening) can be employed as the local codes. Based this new structure, we propose three constructions of vector LRCs with small sub-packetization levels and small repair bandwidth, whose required field sizes are comparable to the code lengths. Additionally, the first two constructions offer a flexible tradeoff between the sub-packetization level and the repair bandwidth, while the third construction has a sub-packetization level of 2, making it easy to implement. Compared to existing vector LRCs, the new vector LRCs provide significantly smaller sub-packetization levels and support a wider range of parameters.

Redundancy transitioning enables erasure-coded storage to adapt to varying performance and reliability requirements by re-encoding data with new coding parameters on-the-fly. Existing studies focus on bandwidth-driven redundancy transitioning that reduces the transitioning bandwidth across storage nodes, yet the actual redundancy transitioning performance remains bottlenecked by the most loaded node. We present BART, a load-balanced redundancy transitioning scheme that aims to reduce the redundancy transitioning time via carefully scheduled parallelization. We show that finding an optimal load-balanced solution is difficult due to the large solution space. Given this challenge, BART decomposes the redundancy transitioning problem into multiple sub-problems and solves the sub-problems via efficient heuristics. We evaluate BART using both simulations for large-scale storage and HDFS prototype experiments on Alibaba Cloud. We show that BART significantly reduces the redundancy transitioning time compared with the bandwidth-driven approach.

Driven by digital twin (DT) technology, the industrial Internet of Things (IIoT) is expanding to open up new frontiers in industrial applications. However, traditional DT modeling approaches require synchronizing massive amounts of data, resulting in high communications overhead and privacy vulnerability. To address this problem, this article proposes a novel DT architecture for IIoT, where the DT can showcase the real-time operating status of the industrial environment. Swarm learning (SL) is an emerging decentralized federated learning (FL) technique that eliminates the need of a centralized server. We present a novel credibility-weighted SL scheme to construct the DT models, which improves data security while ensuring the fairness of participants as opposed to conventional FL. In addition, we develop a DT-assisted deep reinforcement learning algorithm for simultaneously optimizing the system reliability and energy consumption of IIoT. Simulation comparisons demonstrate that the proposed scheme outperforms some state-of-the-art benchmarks in terms of both reliability and energy consumption.

Abundant high-rate$(n, k)$minimum storage regenerating (MSR) codes have been reported in the literature. However, most of them require contacting all the surviving nodes during a node repair process, resulting in a repair degree of$d=n-1$. In practical systems, it may not always be feasible to connect and download data from all surviving nodes, as some nodes may be unavailable. Therefore, there is a need for MSR code constructions with a repair degree of$d < n-1$. Up to now, only a few$(n, k)$MSR code constructions with repair degree$d < n-1$have been reported, some have a large sub-packetization level, a large finite field, or restrictions on the repair degree$d$. In this paper, we propose a new$(n, k)$MSR code construction that works for any repair degree$d>k$, and has a smaller sub-packetization level or finite field than some existing constructions. Additionally, in conjunction with a previous generic transformation to reduce the sub-packetization level, we obtain an MDS array code with a small sub-packetization level and$(1+\epsilon)$-optimal repair bandwidth (i.e.,$(1+\epsilon)$times the optimal repair bandwidth) for repair degree$d=n-1$. This code outperforms some existing ones in terms of either the sub-packetization level or the field size.

We study two problems of private matrix multiplication, over a distributed computing system consisting of a master node, and multiple servers that collectively store a family of public matrices using Maximum-Distance-Separable (MDS) codes. In the first problem of Private and Secure Matrix Multiplication (PSMM) from colluding servers, the master intends to compute the product of its confidential matrix$\mathbf {A}$with a target matrix stored on the servers, without revealing any information about$\mathbf {A}$and the index of target matrix to some colluding servers. In the second problem of Fully Private Matrix Multiplication (FPMM) from colluding servers, the matrix$\mathbf {A}$is also selected from another family of public matrices stored at the servers in MDS form. In this case, the indices of the two target matrices should both be kept private from colluding servers. We develop novel strategies for the two PSMM and FPMM problems, which simultaneously guarantee information-theoretic data/index privacy and computation correctness. We compare the proposed PSMM strategy with a previous PSMM strategy with a weaker privacy guarantee (non-colluding servers), and demonstrate substantial improvements over the previous strategy in terms of communication and computation overheads. Moreover, compared with a baseline FPMM strategy that uses the idea of Private Information Retrieval (PIR) to directly retrieve the desired matrix multiplication, the proposed FPMM strategy significantly reduces storage overhead, but slightly incurs large communication and computation overheads.

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.

In the literature, most of the known high-rate$(n,k)$MDS array codes with the optimal repair property only support a single repair degree (i.e., the number of helper nodes contacted during a repair process)$d$, where$k\le d\le n-1$. However, in practical storage systems, the number of available nodes changes frequently. Thus, it is preferred to construct$(n,k)$MDS array codes with multiple repair degrees and the optimal repair property for all nodes. To the best of our knowledge, only two high-rate MDS array codes have such properties in the literature, which were proposed by Ye and Barg (IEEE Trans. Inform. Theory, 63(10), 2001–2014, 2017). However, their sub-packetization levels are relatively large. In this paper, we present a generic construction method that can convert some MDS array codes with a single repair degree into ones with multiple repair degrees and optimal repair property for a set of nodes, while the repair efficiency/degrees of the remaining nodes can be kept. As an application of the generic construction method, an explicit construction of high-rate MDS array code with multiple repair degrees and the optimal access property for all nodes is obtained over a small finite field by choosing the code proposed by Vajha et al. as the base code. Especially, the sub-packetization level is much smaller than that of the two codes proposed by Ye and Barg concerning the same parameters$n$and$k$.

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.

This work considers the problem of privately outsourcing the computation of a matrix product over a finite field${\mathbb {F}}_{q}$to$N$helper servers. These servers are considered to be honest but curious,i.e., they behave according to the protocol but will try to deduce information about the user’s data. Furthermore, any set of up to$X$servers is allowed to share their data. Previous works considered this collusion a hindrance and the download cost of the schemes increases with growing$X$. We propose to utilize such linkage between servers to the user’s advantage by allowing servers to cooperate in the computational task. This leads to a significant gain in the download cost for the proposed schemes. The gain naturally comes at the cost of increased communication load between the servers. Hence, the proposed cooperative schemes can be understood as outsourcing both computational cost and communication cost. Both information–theoretically secure and computationally secure schemes are considered, showing that allowing information leakage that is computationally hard to utilize will lead to further gains. The proposed server cooperation is then exemplified for specific secure distributed matrix multiplication (SDMM) schemes and linear private information retrieval (PIR). Similar ideas naturally apply to many other use cases as well, but not necessarily always with lowered costs.

For high-rate linear systematic maximum distance separable (MDS) codes, most early constructions could initially optimally repair all the systematic nodes but not all the parity nodes. Fortunately, this issue was first solved by Liet al.in (IEEE Trans. Inform. Theory, 64(9), 6257-6267, 2018), where a transformation that can convert any nonbinary MDS array code into another one with desired properties was proposed. However, the transformation does not work for binary MDS array codes. In this paper, we address this issue by proposing another generic transformation that can convert any$[n, k]$binary MDS array code into a new one, which endows any$r=n-k\ge 2$chosen nodes with optimal repair bandwidth and optimal rebuilding access properties, and at the same time, preserves the normalized repair bandwidth/rebuilding access for the remaining$k$nodes under some conditions. As two immediate applications, we show that 1) by applying the transformation multiple times, any binary MDS array code can be converted into one with optimal rebuilding access for all nodes, 2) any binary MDS array code with optimal repair bandwidth or optimal rebuilding access for the systematic nodes can be converted into one with the corresponding optimality property for all nodes.

Recently, some high-rate maximum distance separable (MDS) array codes were designed to optimally repair a single failed node by connecting all the surviving nodes. However, in practical systems, sometimes not all the surviving nodes are available. To facilitate the practical storage system, a few constructions of$(n,k)$MDS array codes with the property that any single failed node can be optimally repaired by accessing any$d$surviving nodes (i.e., minimum-storage regenerating (MSR) codes) have been proposed, where$d\in [k+1:n-1)$. However, all high-rate MDS array codes with this property either have large sub-packetization levels or are not explicit for all the parameters. To address these issues, we propose a generic transformation that can convert any$(n',k')$MDS array/scalar code to another$(n=n'-\delta,k=k'-\delta)$MDS array code with the optimal repair property and optimal access property for an arbitrary set of two nodes, while the repair efficiency of the remaining$n-2$nodes can be kept, where$2\le \delta \le n'-k'$. By recursively applying the generic transformation to an MDS scalar code multiple times, we get a high-rate MDS array code with the optimal repair property and the optimal access property for all nodes, which outperforms previous known high-rate MDS array codes in terms of either the sub-packetization level or the flexibility of the parameters.

In this paper, we study the problem ofprivate and secure distributed matrix multiplication (PSDMM), where a user having a private matrix$A$and$N$non-colluding servers sharing a library of$L$($L>1$) matrices$B^{(0)}, B^{(1)},\ldots,B^{(L-1)}$, for which the user wishes to compute$AB^{(\theta)}$for some$\theta \in [0, L$) without revealing any information of the matrix$A$to the servers, and keeping the index$\theta $private to the servers. Previous work is limited to the case that the shared library (i.e.,the matrices$B^{(0)}, B^{(1)},\ldots,B^{(L-1)}$) is stored across the servers in a replicated form and schemes are very scarce in the literature, there is still much room for improvement. In this paper, we propose two PSDMM schemes, where one is limited to the case that the shared library is stored across the servers in a replicated form but has a better performance than state-of-the-art schemes in that it can achieve a smaller recovery threshold and download cost. The other one focuses on the case that the shared library is stored across the servers in an MDS-coded form, which requires less storage in the servers. The second PSDMM code does not subsume the first one even if the underlying MDS code is degraded to a repetition code as they are totally two different schemes.

In this work, two practical concepts related to private information retrieval (PIR) are introduced and coinedfull support-rankPIR andstrongly linearPIR. Being of full support-rank is a technical, yet natural condition required to prove a converse result for a capacity expression and satisfied by almost all currently known capacity-achieving schemes, while strong linearity is a practical requirement enabling implementation over small finite fields with low subpacketization degree. Then, the capacity of MDS-coded, linear, full support-rank PIR in the presence of colluding servers is derived, as well as the capacity of symmetric, linear PIR with colluding, adversarial, and nonresponsive servers for the recently introduced concept of matched randomness. This positively settles the capacity conjectures stated by Freij-Hollantiet al.and Tajeddineet al.in the presented cases. It is also shown that, further restricting to strongly-linear PIR schemes with deterministic linear interference cancellation, the so-called star product scheme proposed by Freij-Hollantiet al.is essentially optimal and induces no capacity loss.

Consider the problem of a user having a private matrix$A$and$N$non-colluding servers sharing a library of$L (L > \ 1)$matrices$B^{(0)}, B^{(1)},\ldots, B^{(L-1)}$, for which the user wishes to compute$AB^{(\theta)}$for some$\theta\in[0, L)$without revealing any information of the matrix$A$to the servers, and keeping the index$\theta$private to the servers. This problem is known as private and secure distributed matrix multiplication (PSDMM) and is supposed to have wide application potential. However, studies of PSDMM are still scarce in the literature. In this paper, we propose a new efficient private and secure distributed matrix multiplication coding scheme, which has a better performance than state-of-the-art schemes in that it achieves a smaller recovery threshold and download cost as well as providing a more flexible tradeoff between the upload and download costs.

Coded caching systems have been widely studied to reduce the data transmission during the peak traffic time. In practice, two important parameters of a coded caching system should be considered, i.e., the transmission rate which is the maximum amount of the data transmission during the peak traffic time, and the subpacketization level, the number of divided packets of each file when we implement a coded caching scheme. Although there exists a tradeoff between transmission rate and subpacketization, we prefer to design a scheme with transmission rate and subpacketization as small as possible since they reflect the transmission efficiency and complexity of the caching scheme, respectively. In this paper, we first characterize a coded caching scheme from the viewpoint of linear algebra and show that designing a linear coded caching scheme is equivalent to constructing three classes of matrices satisfying some rank conditions. Then based on the invariant subspaces in linear algebra and combinatorial design theory, a new class of coded caching schemes over F2is obtained by constructing these three classes of matrices. It turns out that the transmission rate of our new scheme is the same as the scheme construct by Yan et al. (IEEE Trans. Inf. Theory 63, 5821-5833, 2017), but the subpacketization is significantly reduced. Finally by means of these matrices, we show that the minimum storage regenerating codes can also be used to construct coded caching schemes.

In the literature, all the known high-rate MDS codes with the optimal repair bandwidth possess a significantly large sub-packetization level, which may prevent the codes to be implemented in practical systems. To build MDS codes with small sub-packetization level, existing constructions and theoretical bounds imply that one may sacrifice the optimality of the repair bandwidth. Partly motivated by the work of Tamo et al. (IEEE Trans. Inform. Theory, 59(3), 1597-1616, 2013), in this paper, we present a transformation that can greatly reduce the sub-packetization level of MDS codes with the optimal repair bandwidth with respect to the same code length n. As applications of the transformation, four high-rate MDS codes having both small sub-packetization level and near-optimal repair bandwidth can be obtained, where three of them are explicit and the required field sizes are around or even smaller than the code length n. Additionally, we propose another explicit MDS code which has a similar structure as that of the first resultant code obtained by the generic transformation, but can be built on a smaller finite field.

Private information retrieval (PIR) is the problem of privately retrieving one out of M original files from N severs, i.e., each individual server gains no information on the identity of the file that the user is requesting. Usually, the M files are replicated or encoded by a maximum distance separable (MDS) code and then stored across the N servers. Compared to mere replication, MDS-coded servers can significantly reduce the storage overhead. Particularly, PIR from minimum storage regenerating (MSR) coded servers can simultaneously reduce the repair bandwidth when repairing failed servers. Existing PIR protocols from MSR-coded servers either require large sub-packetization levels or are not capacity-achieving. In this paper, a PIR protocol from MDS array codes is proposed, subsuming PIR from MSR-coded servers as a special case. Particularly, only the case of non-colluding, honest-but-curious servers is considered. The retrieval rate of the new PIR protocol achieves the capacity of PIR from MDS-/MSR-coded servers. By choosing different MDS array codes, the new PIR protocol can have varying advantages when compared with existing protocols, e.g., 1) small sub-packetization, 2) (near-)optimal repair bandwidth, 3) implementable over the binary field F2.

In the literature, all the known high-rate MDS codes with the optimal repair bandwidth possess a significantly large sub-packetization level, which may prevent the codes to be implemented in practical systems. To build MDS codes with small sub-packetization level, existing constructions and theoretical bounds imply that one may sacrifice the optimality of the repair bandwidth. Partly motivated by the work of Tamo et al. (IEEE Trans. Inform. Theory, 59(3), 1597-1616, 2013), in this paper, we present a powerful transformation that can greatly reduce the sub-packetization level of any MDS codes with respect to the same code length n. As applications of the transformation, four high-rate MDS codes having both small sub-packetization level and near optimal repair bandwidth can be obtained, where two of them are also explicit and the required field sizes are comparable to the code length n.

In last ISIT, we reported a generic transformation on maximum distance separable (MDS) codes, which can convert any non-binary (k+r, k) MDS code into another (k+r, k) MDS code such that an arbitrarily chosen r nodes will have the optimal repair bandwidth and the optimal rebuilding access by modifying their data. However, the resultant code thus obtained is no longer in a systematic form if we wish to optimal repair r systematic nodes, and another linear transformation is needed to convert it into one, which may break the inherent simplicity in the decoding and repair procedure. In this work, we propose an alternative generic transformation to solve this issue. In the alternative generic transformation, any r systematic nodes can be optimally repaired with their data keeping unchanged through instead modifying the data on the r parity nodes. As a result, by applying multiple times the two transformations in combination, we can directly obtain systematic MDS codes with optimal rebuilding access for all nodes or for a subset of nodes from any non-binary scalar MDS codes, which have the optimal sub-packatization level as well.

Up to now, many (k + r, k, N) minimum-storage regenerating (MSR) codes with k information nodes, r parity nodes, and node capacity N have been proposed. However, most of them are constructed over a relatively large finite field. In this paper, we propose three high-rate MSR codes over small finite fields. First, the new MSR code C1with the optimal access property for all nodes is constructed over small finite field Fq, for example q = 3 for even r or q ≥ r + 1 for odd r, which is much smaller than that of the known one given by Ye and Barg. Further, considering to reduce the node capacity, another new MSR code C2over Fqwith q ≥ r + 2 is generated based on C1, which can effectively reduce the node capacity of C1by a factor of rr-1. However, only the first k nodes of C2have the optimal access property. Therefore, the new MSR code C3over Fqwith q ≥ r + 2 which has the optimal access property for all nodes is proposed by modifying C2. Notably, in contrast to C1, the node capacity of C3is decreased by a factor of rr-2.

We propose a generic transformation that can convert any nonbinary (n = k + r, k) maximum distance separable (MDS) code into another (n, k) MDS code over the same field such that: 1) some arbitrarily chosen r nodes have the optimal repair bandwidth and the optimal rebuilding access; 2) for the remaining k nodes, the normalized repair bandwidth and the normalized rebuilding access (over the file size) are preserved; and 3) the sub-packetization level is increased only by a factor of r. Two immediate applications of this generic transformation are then presented. The first application is that we can transform any nonbinary MDS code with the optimal repair bandwidth or the optimal rebuilding access for the systematic nodes only, into a new MDS code which possesses the corresponding repair optimality for all nodes. The second application is that by applying the transformation multiple times, any nonbinary (n, k) scalar MDS code can be converted into an (n, k) MDS code with the optimal repair bandwidth and the optimal rebuilding access for all nodes, or only a subset of nodes, whose sub-packetization level is also optimal.

We propose a generic transformation on maximum distance separable (MDS) codes, which can convert any non-binary (k+r, k) MDS code into another (k+r, k) MDS code with the following properties: 1) An arbitrarily chosen r nodes will have the optimal repair bandwidth and the optimal rebuilding access, 2) the repair bandwidth and rebuilding access efficiencies of all other nodes are maintained as in the code before the transformation, 3) it uses the same finite field as the code before the transformation, and 4) the sub-packetization is increased only by a factor of r. As two immediate applications of this powerful transformation, we show that 1) any non-binary MDS code with optimal repair bandwidth, or optimal rebuilding access, for only systematic nodes can be converted into an MDS code with the corresponding repair optimality for all nodes; and 2) any non-binary scalar MDS code can be converted to an MDS code with optimal repair bandwidth and rebuilding access for all nodes, or to an MDS code with optimal rebuilding access for all systematic nodes and moreover with the optimal sub-packatization, by applying the transformation multiple times.

In this paper, we reinterpret the (k+2, k) zigzag code in coding matrix and then propose an optimal exact repair strategy for its parity nodes, whose repair disk I/O approaches a lower bound derived in this paper.

In this paper, we present a generic framework for constructing systematic minimum storage regenerating codes with two parity nodes based on the invariant subspace technique. Codes constructed in our framework not only contain some best known codes as special cases, but also include some new codes with key properties, such as the optimal access property and the optimal update property. In particular, for a given storage capacity of an individual node, one of the new codes has the largest number of systematic nodes and two of the new codes have the largest number of systematic nodes with the optimal update property.

The newly presented (k + m, k) Hadamard minimum storage regenerating (MSR) codes are a class of high rate storage codes with optimal repair property for single node failure. In this paper, we propose a new simple optimal repair strategy for (k + m, k) Hadamard MSR codes, which can considerably reduce the computation compared with the original one during the node repair.

Piggybacking is an efficient method to decrease the repair bandwidth of maximum distance separable codes. In this paper, in order to reduce the repair bandwidth of parity nodes of the known minimum storage regenerating (MSR) codes with high rate, which is usually the whole amount of the original data, i.e., the maximal, a new systematic piggybacking design is proposed through an in-depth analysis of the design of piggybacking. As a result, new MSR codes are obtained with almost optimal repair bandwidth of parity nodes while retaining the optimal repair bandwidth of systematic nodes. Furthermore, MSR codes with balanced download during node repair process are presented based on the new piggybacking design.