In distributed computing systems, coding has played an important role to robustify the system against the effect of noise, e.g., stragglers, system failures and communication bottlenecks. Most of the existing work has focused on a simple master-worker model with one master and homogeneous workers. However, real-world systems are typically configured with heterogeneous workers distributed to computing nodes and serve multiple tasks in parallel. In this study, we consider the scenario in which multiple masters perform matrix multiplications using the workers having group heterogeneity. The group heterogeneity models that homogeneous workers are located in the same location and regarded as a group; the workers deployed in the different locations are potentially heterogeneous. We propose an asymptotically optimal worker assignment to multiple masters for coded distributed computing in the presence of heterogeneous groups of workers. Specifically, we present a lower bound for the expected latency in terms of the numbers of workers assigned to the masters and the amount of tasks allocated to workers. Adding the concentration constraints on the number of workers allocated to masters, we can obtain the minimum of the lower bound by taking the optimal worker assignment. We find the optimal worker assignment by converting the problem at hand into a linear programming problem. From both numerical simulations and experiments on Amazon EC2 clusters, we confirm that the effect of the proposed worker assignment is significant in various scenarios.

Recently, coding has been a useful technique to mitigate stragglers' effect in distributed computing. However, coding in this context has been mainly explored assuming homogeneous workers, although real-world clusters often consist of heterogeneous workers with different computing capabilities. The uniform load allocation without considering the heterogeneity possibly causes a significant loss in latency. In this article, we suggest the optimal load allocation for coded distributed computing with heterogeneous workers. Specifically, we focus on the scenario that there exist workers having the same computing capability, which can be regarded as a group for analysis. We rely on the lower bound on the expected latency and obtain the optimal load allocation by showing that our load allocation achieves the minimum of the lower bound for a sufficiently large number of workers. Given the proposed optimal load allocation, we derive the optimal code rate to achieve the minimum expected latency. From numerical simulations, when assuming the group heterogeneity, our load allocation reduces the expected latency by orders of magnitude over the existing scheme. Furthermore, from experiments on Amazon EC2 for scenarios with distinct straggler/heterogeneity patterns, we observe that our scheme outperforms the competing schemes reducing the total finishing time by up to 52%.

We study the potential enhancement of the read access speed in high-performance solid-state drives (SSDs) by coding, given speed variations across the multiple flash interfaces and assuming occasional local memory failures. Our analysis is based on a queuing model that incorporates both read request failures and NAND element failures. The NAND element failure in the present context reflects various limitations on the memory element level such as bad blocks, dies or chips that cannot be corrected by error control coding (ECC) typically employed to protect pages read off the NAND cells. Our analysis provides a clear picture of the storage-overhead and read-latency trade-offs given read failures and NAND element failures. We investigate two different ways to mitigate the effect of NAND element failures using the notion of multi-class jobs with different priorities. A strong motivation for this work is to understand the reliability requirement of NAND chip components given an additional layer of failure protection, under the latency/storage-overhead constraints.

In this paper, we consider the straggler problem of the high-dimensional matrix multiplication over distributed workers. To tackle this problem, we propose an irregular-product-coded computation, which is a generalized scheme of the standard-product-coded computation proposed in [1]. Introducing the irregularity to the product-coded matrix multiplication, one can further speed up the matrix multiplication, enjoying the low decoding complexity of the product code. The idea behind the irregular product code introduced in [2] is allowing different code rates for the row and column constituent codes of the product code. We provide a latency analysis of the proposed irregular-product-coded computation. In terms of the total execution time, which is defined by a function of the computation time and decoding time, it is shown that the irregular-product-coded scheme outperforms other competing schemes including the replication, MDS-coded and standard-product-coded schemes in a specific regime.

Coding for distributed computing supports low-latency computation by relieving the burden of straggling workers. While most existing works assume a simple master-worker model, we consider a hierarchical computational structure consisting of groups of workers, motivated by the need to reflect the architectures of real-world distributed computing systems. In this work, we propose a hierarchical coding scheme for this model, as well as analyze its decoding cost and expected computation time. Specifically, we first provide upper and lower bounds on the expected computing time of the proposed scheme. We also show that our scheme enables efficient parallel decoding, thus reducing decoding costs by orders of magnitude over non-hierarchical schemes. When considering both decoding cost and computing time, the proposed hierarchical coding is shown to outperform existing schemes in many practical scenarios.

Distributed storage systems suffer from significant repair traffic generated due to the frequent storage node failures. This paper shows that properly designed low-density parity-check (LDPC) codes can substantially reduce the amount of required block downloads for repair thanks to the sparse nature of their factor graph representation. In particular, with a careful construction of the factor graph, both low repair-bandwidth and high reliability can be achieved for a given code rate. First, a formula for the average repair bandwidth of LDPC codes is developed. This formula is then used to establish that the minimum repair bandwidth can be achieved by forcing a regular check node degree in the factor graph. Moreover, it is shown that given a fixed code rate, the variable node degree should also be regular to yield minimum repair bandwidth, under some reasonable minimum variable node degree constraint. It is also shown that for a given repair-bandwidth requirement, LDPC codes can yield substantially higher reliability than the currently utilized Reed-Solomon codes. Our reliability analysis is based on a formulation of the general equation for the mean-time-to-data-loss (MTTDL) associated with LDPC codes. The formulation reveals that the stopping number is closely related to the MTTDL. It is further shown that LDPC codes can be designed such that a small loss of repair-bandwidth optimality may be traded for a large improvement in erasure-correction capability and thus the MTTDL.

We study potential enhancement of the read access speed in high-performance solid-state drives (SSDs) by coding, given speed variations across the multiple flash interfaces and assuming occasional local memory failures. Our analysis is based on a queuing model that incorporates both read request failures and node failures. It provides a clear picture on the coding-overhead and read-access-time trade-offs given read failures and node failures. The node failure in the present context reflects various limitations on the memory element level such as page failures, block failures or channel failures that occur during the access of stored data from NAND flash memory chips. A strong motivation for this work is to understand the reliability requirement of NAND chip components given a layer of erasure protection across nodes, under the latency/storage-overhead constraints.

Distributed storage systems suffer from significant repair traffic generated due to frequent storage node failures. This paper shows that properly designed low-density parity-check (LDPC) codes can substantially reduce the amount of required block downloads for repair thanks to the sparse nature of their factor graph representation. In particular, with a careful construction of the factor graph, both low repair-bandwidth and high reliability can be achieved for a given code rate. First, a formula for the average repair bandwidth of LDPC codes is developed. This formula is then used to establish that the minimum repair bandwidth can be achieved by forcing a regular check node degree in the factor graph. It is also shown that for a given repair-bandwidth overhead, LDPC codes can have substantially higher reliability than currently utilized Reed-Solomon (RS) codes. Our reliability analysis is based on a formulation of the general equation for the mean-time-to-data-loss (MTTDL) associated with LDPC codes. The formulation reveals that the stopping number is highly related to MTTDL. For code rates 1/2, 2/3, and 3/4, our results show that quasi-cyclic (QC) progressive-edge-growth (PEG) LDPC codes with variable node degree 2 allow 25% ~ 50% reduction in the repair bandwidth while maintaining higher MTTDL compared to currently employed RS codes.

In modern tape storage, user data are recorded and retrieved along multiple tracks of rapidly moving, flexible magnetic medium that give rise to a variety of channel impediments including occasional long erasures, more frequent amplitude fades as well as a large amount of random errors. This work considers reliable recovery of data from such tape channels using a novel concatenation of an inner Reed-Solomon (RS) code and an outer nonbinary low-density parity-check (LDPC) code. This particular concatenation scheme and a highly tailored iterative decoding algorithm are chosen to efficiently handle the assortment of the tape channel impediments while meeting the stringent target error rate constraint as well as key practical requirements of the mass tape storage system. Despite the use of a nonbinary LDPC code, the proposed scheme allows excellent performance-complexity tradeoffs. In stark contrast to any existing coding schemes that involve LDPC codes, the proposed concatenation strategy allows semianalytic error rate performance evaluation at rates below what is possible using modern computers, thus providing an ability to ensure satisfactory low-error-rate performance.