Matrix multiplication is a crucial operation in many data-intensive workloads. Given the large size of matrices in today's workloads, it is common to split the computation into tasks executed on different servers. As stragglers are common in distributed computing, various coding schemes have been proposed to mitigate stragglers, including some even leveraging the partially completed results from stragglers by splitting each task into subtasks. However, existing schemes have ignored the order of execution, making them unnecessarily complex for encoding and decoding. In this paper, we propose a series of constructions of straggler-leveraging coding schemes for matrix multiplication. We consider the execution order of subtasks and then construct the coding schemes based on the probability of an uncoded subtask being recovered by a coded subtask. As a result, our coding schemes can significantly save the encoding and decoding complexities while maintaining an arbitrarily controllable recoverability of incomplete uncoded subtasks.

Matrix multiplication is a foundational building block in various data-intensive workloads. With the fast-increasing sizes of workloads, it is common to split the job of matrix multiplication into multiple tasks and execute them on different servers in parallel. However, stragglers which perform slower than other servers are inevitable in distributed computing. Running coded tasks can tolerate the same number of stragglers with much fewer servers compared to replicating tasks on multiple servers. Although stragglers only partially complete their tasks, they can also be utilized toward a faster completion of the job, by uploading the results of sub-tasks split from each task. Existing designs utilizing partially completed tasks assume that all sub-tasks have an equal probability of being incomplete and require all input data to generate coded sub-tasks. However, not any arbitrary placement of incomplete sub-tasks is valid when sub-tasks are executed sequentially. If we only consider valid placements of incomplete sub-tasks, each coded sub-tasks can be encoded from much less input data, significantly saving the encoding complexity. In this paper, we introduce a new coding scheme called Sequence-Aware Coding (SAC), which exploits only valid placements of incomplete sub-tasks to reduce the encoding complexity while still leveraging the results of sub-tasks on stragglers.

Gradient methods, such as gradient descent, are widely deployed to train optimization-based models in machine learning. To train such models on a large dataset, the dataset is commonly split into multiple partitions which are trained on different workers. In order to tolerate stragglers, existing techniques either use gradient coding (GC) to recover the full gradients from a certain number of workers or recover gradients partially from an arbitrary number of workers. In this paper, we propose ignore-straggler gradient coding (IS-GC) that allows GC to tolerate an arbitrary number of stragglers. Compared to approximated gradient descent, IS-GC can recover more gradients when there is the same number of stragglers. We design a graph-based model to decode coded gradients from an arbitrary number of stragglers, and prove that it can maximize the recovery of gradients. We apply IS-GC on fractional repetition (FR) and cyclic repetition (CR), two representative dataset placement schemes of GC. We also propose hybrid repetition (HR) that generalizes over FR and CR and achieves a flexible trade-off between FR and CR. With extensive experiments, we demonstrate that IS-GC can flexibly tolerate an arbitrary number of stragglers and achieve a low completion time of training.

Multi-level erasure coding (MLEC) has seen large deployments in the field, but there is no in-depth study of design considerations for MLEC at scale. In this paper, we provide comprehensive design considerations and analysis of MLEC at scale. We introduce the design space of MLEC in multiple dimensions, including various code parameter selections, chunk placement schemes, and various repair methods. We quantify their performance and durability, and show which MLEC schemes and repair methods can provide the best tolerance against independent/correlated failures and reduce repair network traffic by orders of magnitude. To achieve this, we use various evaluation strategies including simulation, splitting, dynamic programming, and mathematical modeling. We also compare the performance and durability of MLEC with other EC schemes such as SLEC and LRC and show that MLEC can provide high durability with higher encoding throughput and less repair network traffic over both SLEC and LRC.

Coded distributed computation has become common practice for performing gradient descent on large datasets to mitigate stragglers and other faults. This paper proposes a novel algorithm that encodes the partial derivatives themselves and furthermore optimizes the codes by performing lossy compression on the derivative codewords by maximizing the information contained in the codewords while minimizing the information between the codewords. The utility of this application of coding theory is a geometrical consequence of the observed fact in optimization research that noise is tolerable, sometimes even helpful, in gradient descent based learning algorithms since it helps avoid overfitting and local minima. This stands in contrast with much current conventional work on distributed coded computation which focuses on recovering all of the data from the workers. A second further contribution is that the low-weight nature of the coding scheme allows for asynchronous gradient updates since the code can be iteratively decoded; i.e., a worker’s task can immediately be updated into the larger gradient. The directional derivative is always a linear function of the direction vectors; thus, our framework is robust since it can apply linear coding techniques to general machine learning frameworks such as deep neural networks.

Matrix multiplication is a fundamental building block in various distributed computing algorithms. In order to multiply large matrices, it is common practice to distribute the computation into multiple tasks running on different nodes. In order to tolerate stragglers among such nodes, various coding schemes have been proposed by adding additional coded tasks. However, most existing coding schemes for matrix multiplication are constructed for only one matrix multiplication, while batch matrix multiplication is common in large-scale distributed computing workloads. In this paper, we propose Rook Coding (RC), a novel polynomial-based coding framework for computing the multiplication of$n$pairs of matrices in batch. Designed to achieve lower encoding time in practice, we construct RC as polynomials of much simpler forms than existing coding schemes for batch matrix multiplication, achieving a recovery threshold of$O(n^{\log _{2} ~3})$. Compared to existing coding schemes, RC achieves a lower encoding complexity in practice, because of its simpler forms in the encoding polynomials. Through extensive experiments, we show that RC can save the time of the whole job thanks to its low overhead of encoding.

The matrix multiplication is a fundamental building block in many machine learning models. As the input matrices may be too large to be multiplied on a single server, it is common to split input matrices into multiple submatrices and execute the multiplications on different servers. However, in a distributed infrastructure it is common to observe stragglers whose performance is lower than other servers at some time. In order to mitigate the adversarial effects of potential stragglers, various coding schemes for the distributed matrix multiplication have been recently proposed. While most existing works have only considered the simplest case where only two matrices are multiplied, we investigate a more general case in this paper where multiple matrices are multiplied, and propose a coding scheme that the result can be directly decoded in one round, instead of in multiple rounds of computation. Compared to completing the matrix chain multiplication in multiple rounds, our coding scheme can achieve significant savings of completion time by up to 90.3%.

Distributed storage systems provide cloud storage services by storing data on commodity storage servers. Conventionally, data are protected against failures of such commodity servers by replication. Erasure coding consumes less storage overhead than replication to tolerate the same number of failures and thus has been replacing replication in many distributed storage systems. However, with erasure coding, the overhead of reconstructing data from failures also increases significantly. Under the ever-changing workload where data accesses can be highly skewed, it is challenging to deploy erasure coding with appropriate values of parameters to achieve a well trade-off between storage overhead and reconstruction overhead. In this paper, we propose Zebra, a framework that encodes data by their demand into multiple tiers that deploy erasure codes with different values of parameters. Zebra automatically determines the number of such tiers and dynamically assigns erasure codes with optimal values of parameters into corresponding tiers. With Zebra, a flexible trade-off between storage overhead and reconstruction overhead is achieved with multiple tiers. When demand changes, Zebra adjusts itself with a marginal amount of network transfer. We demonstrate that Zebra can work with two representative families of erasure codes in distributed storage systems, Reed-Solomon codes and local reconstruction codes.

Matrix multiplication is a fundamental building block in various distributed computing algorithms. In order to compute the multiplication of large matrices, it is common practice to distribute the computation into multiple tasks running on different nodes. In order to tolerate potential stragglers among such nodes, various coding schemes have been proposed which add additional coded tasks. However, most existing coding schemes for the matrix multiplication are constructed for only one matrix multiplication, while it is common to compute multiple matrix multiplications concurrently in large-scale distributed computing workloads. In this paper, we propose a novel coding framework where the results of multiple multiplications can be obtained within one job concurrently. Compared with running the multiplications separately with multiple jobs, our work demonstrates that the same number of stragglers can be tolerated with much fewer tasks.

Matrix multiplication is a fundamental operation in various machine learning algorithms. With the size of the dataset increasing rapidly, it is now a common practice to compute the large-scale matrix multiplication on multiple servers, with each server running a task that multiplies submatrices of input matrices. As straggling servers are inevitable in a distributed infrastructure, various coding schemes, which deploy coded tasks encoded from input matrices, have been proposed. The overall result can then be decoded from a subset of such coded tasks. However, as resources are shared with other jobs in a distributed infrastructure and their performance can change dynamically, the optimal way to encode the input matrices may also change with time. So far, existing coding schemes for the matrix multiplication all require splitting the input matrices and encoding them in advance, and cannot change the coding schemes or adjust their parameters after encoding. In this paper, we propose a framework that can change the coding schemes and their parameters, by only locally re-encoding each task on each server. We demonstrate that the original tasks can be re-encoded into new tasks only incurring marginal overhead.

With the increasing sizes of models and datasets, it has become a common practice to split machine learning jobs as multiple tasks. However, stragglers are inevitable when running a job on multiple servers. Compared to replicating each task on multiple servers, running coded tasks can tolerate the same number of stragglers with much fewer servers. However, additional results of tasks running on stragglers are typically disregarded in existing schemes of coded computing, incurring a waste of the resources on such servers. In this paper, we leverage the results of partially finished tasks. In existing designs that utilize partially finished tasks, they have only considered servers with homogeneous performance. However, in a typical distributed infrastructure, e.g., a cloud, servers with heterogeneous configurations are common. Therefore, we propose Spinner which can efficiently utilize the results of partially finished tasks even on heterogeneous servers. Spinner works with existing coding schemes for matrix multiplication, a fundamental operation in various machine learning algorithms, and can efficiently assign the workload based on the performance of the corresponding server. Furthermore, Spinner can equivalently adapt the coding scheme for heterogeneous servers, aligned with the expected workload assigned to each server, and thus save the complexity of decoding. Combining the two strategies together, we demonstrate in our experiments that Spinner can improve the time of matrix multiplication by up to 84.0% and thus improve the time of linear regression by 40.7%.

Matrix multiplication is a fundamental building block in various machine learning algorithms. When the matrix comes from a large dataset, the multiplication can be split into multiple tasks which calculate the multiplication of submatrices on different nodes. As some nodes may be stragglers, coding schemes have been proposed to tolerate stragglers in such distributed matrix multiplication. However, existing coding schemes typically split the matrices in only one or two dimensions, limiting their capabilities to handle large-scale matrix multiplication. Three-dimensional coding, however, does not have any code construction that achieves the optimal number of tasks required for decoding, with the best result achieved by entangled polynomial (EP) codes. In this paper, we propose dual entangled polynomial (DEP) codes that require around 25% fewer tasks than EP codes by executing two matrix multiplications on each task. With experiments in a real cloud environment, we show that DEP codes can also save the decoding overhead and memory consumption of tasks.

Distributed storage systems store a substantial amount of data in a large number of servers built with commodity hardware. In order to protect data against server failures, erasure coding has been deployed in many distributed storage systems because of its low storage overhead. In particular, since disk I/O is, in many cases, a bottleneck in the distributed storage system, locally repairable codes, have been proposed that incur low volumes of disk I/O when reconstructing missing data after server failures. However, since original data can only be read from specific servers, existing designs of locally repairable codes suffer from limited data parallelism. Besides, if the performance of servers is heterogeneous, slow servers may become the bottleneck when accessing data in parallel. In this paper, we propose Galloper codes, a novel family of locally repairable codes, that achieve low disk I/O during reconstruction and meanwhile extend data parallelism from specific servers to all servers. Moreover, the amount of original data in each server can be arbitrarily determined based on the performance of corresponding servers. We have implemented a prototype of Galloper codes on Apache Hadoop, and our experimental results have shown that Galloper codes can reduce the completion time of MapReduce jobs by up to 42.9%, with a comparable performance as existing locally repairable codes, in terms of disk I/O overhead, as well as encoding and reconstruction overhead.

Deployed in various distributed storage systems, erasure coding has demonstrated its advantages of low storage overhead and high failure tolerance. Typically in an erasure-coded distributed storage system, systematic maximum distance seperable (MDS) codes are chosen since the optimal storage overhead can be achieved and meanwhile data can be read directly without decoding operations. However, data parallelism of existing MDS codes is limited, because we can only read data from some specific servers in parallel without decoding operations. In this paper, we propose Carousel codes, designed to allow data to be read from an arbitrary number of servers in parallel without decoding, while preserving the optimal storage overhead of MDS codes. Furthermore, Carousel codes can achieve the optimal network traffic to reconstruct an unavailable block. We have implemented a prototype of Carousel codes on Apache Hadoop. Our experimental results have demonstrated that Carousel codes can make MapReduce jobs finish with almost 50% less time and reduce data access latency significantly, with a comparable throughput in the encoding and decoding operations and no additional sacrifice of failure tolerance or the network overhead to reconstruct unavailable data.

In distributed storage systems, erasure codes have been increasingly deployed to tolerate server failures without loss of data. Traditional erasure codes, such as Reed-Solomon codes, suffer from a high volume of network transfer and disk I/O to recover unavailable data at failed storage servers. Typically, unavailable data at different failed storage servers in a distributed storage system are fixed separately. It has been shown that it is possible to reduce the volume of network transfer significantly by reconstructing data from multiple storage servers at the same time. However, there has been no construction of erasure codes to achieve it without imposing strict constraints on system parameters. In this paper, we propose Beehive codes, designed for optimizing the volume of network transfers to fix the data on multiple failed storage servers. Beehive codes can be constructed over a wide range of system parameters at code rate no more than 0.5, while incurring slightly more storage overhead than Reed-Solomon codes. To achieve the optimal storage overhead as Reed-Solomon codes, we further extend vanilla Beehive codes to MDS Beehive codes, which incurs near-optimal volumes of network transfers during reconstruction. We implement both Beehive and MDS Beehive Codes in C++ and evaluate their performance on Amazon EC2. Our evaluation results have clearly shown that the volume of both network transfers and disk I/O can be conserved by a substantial margin.

Erasure coding has been increasingly replacing replication in distributed storage systems, thanks to its lower storage overhead with the same level of failure tolerance. However, with lower storage overhead, the reconstruction overhead of erasure codes can increase significantly as well. Under the ever-changing workload, in which the data access can be highly skewed, it is difficult to achieve a well trade-off between the storage overhead and the reconstruction overhead. In this paper, we propose Zebra, a framework that encodes data into multiple tiers by their demand. Given the overall storage overhead and the number of failures to tolerate, Zebra determines the parameters of erasure coding in each tier by solving a geometric programming problem. Based on the demand of data, Zebra can dynamically assign data into the corresponding tiers to minimize the overall reconstruction overhead, and achieve a flexible tradeoff between the storage overhead and the reconstruction overhead in multiple tiers, such that hot data can enjoy less overhead of reconstruction and cold data can be stored with lower storage overhead. When demand changes, Zebra can adjust itself accordingly with a marginal amount of network transfer.

Providing quality-of-service guarantees by means of fair sharing has never been more challenging in datacenters. Due to the heterogeneity of machine configurations, datacenter jobs frequently specify placement constraints, restricting them to run on a particular class of machines meeting specific hardware/software requirements. In addition, jobs have diverse demands across multiple resource types, and may saturate any of the CPU, memory, or storage resources. Despite the rich body of recent work on datacenter scheduling, it remains unclear how multi-resource fair sharing is defined and achieved for jobs with placement constraints. In this paper, we propose a new sharing policy called Task Share Fairness (TSF). With TSF, jobs are better off sharing the datacenter, and are better off reporting demands and constraints truthfully. We have prototyped TSF on Apache Mesos and confirmed its service guarantees in a 50-node EC2 cluster. Trace-driven simulations have further revealed that TSF speeds up 60% of tasks over existing fair schedulers.

Multi-resource fair schedulers have been widely implemented in compute clusters to provide service isolation guarantees. Existing multi-resource sharing policies, notably Dominant Resource Fairness (DRF) and its variants, are designed for unconstrained jobs that can run on all machines in a cluster. However, an increasing number of datacenter jobs specify placement constraints and can only run on a particular class of machines meeting specific hardware/software requirements (e.g., GPUs or a particular kernel version). We show that directly extending existing policies to constrained jobs either compromises isolation guarantees or allows users to gain more resources by deceiving the scheduler. It remains unclear how multi-resource fair sharing is defined and achieved in the presence of placement constraints. We address this open problem by a new sharing policy, called Task Share Fairness (TSF), that provides provable isolation guarantees and is strategy-proof against gaming the allocation policy. TSF is shown to be envy-free and Pareto optimal as well.

Distributed storage systems store redundant data to tolerate failures of storage nodes and lost data should be repaired when storage nodes fail. A class of MDS codes, called minimum-storage regenerating (MSR) codes, has been designed to optimize bandwidth consumption when repairing one single failure. Compared with repairing failures individually, the cooperative repair of multiple failures can help to further save bandwidth consumption when multiple failures are being repaired. In this paper, we present a new construction of minimum-storage cooperative regenerating (MSCR) codes that repair two failures cooperatively and exactly. We show that given a valid instance of linear exact MSR codes, we are able to construct a corresponding repair procedure to repair any two failures cooperatively with optimal bandwidth consumption, i.e., to construct an instance of exact MSCR codes directly from exact MSR codes. With this connection, we are also able to repair any single failure exactly with MSCR codes.

In distributed storage systems, a substantial volume of data are stored in a distributed fashion, across a large number of storage nodes. To maintain data integrity, when existing storage nodes fail, lost data are regenerated at replacement nodes. Regenerating multiple data losses in batches can reduce the consumption of bandwidth. However, existing schemes are only able to achieve lower bandwidth consumption by utilizing a large number of participating nodes. In this paper, we propose a cooperative pipelined regeneration process that regenerates multiple data losses cooperatively with much fewer participating nodes. We show that cooperative pipelined regeneration is not only able to maintain optimal data integrity, but also able to further reduce the consumption of bandwidth as well.

Distributed storage systems provide reliable storage service by storing data, with a certain amount of redundancy, into a substantial number of storage nodes. In order to compensate the data loss incurred by node failures, the lost data should be regenerated. Tree-structured regeneration, during whi

Distributed storage systems provide large-scale reliable data storage by storing a certain degree of redundancy in a decentralized fashion on a group of storage nodes. To recover from data losses due to the instability of these nodes, whenever a node leaves the system, additional redundancy should be regenerated to compensate such losses. In this context, the general objective is to minimize the volume of actual network traffic caused by such regenerations. A class of codes, called regenerating codes, has been proposed to achieve an optimal trade-off curve between the amount of storage space required for storing redundancy and the network traffic during the regeneration. In this paper, we jointly consider the choices of regenerating codes and network topologies. We propose a new design, referred to as RCTREE, that combines the advantage of regenerating codes with a tree-structured regeneration topology. Our focus is the efficient utilization of network links, in addition to the reduction of the regeneration traffic. With the extensive analysis and quantitative evaluations, we show that RCTREE is able to achieve a both fast and stable regeneration, even with departures of storage nodes during the regeneration.

Distributed storage systems, built on peer-to-peer networks, can provide large-scale data storage and high data reliability by redundant schemes, such as replica, erasure codes and linear network coding. Redundant data may get lost due to the instability of distributed systems, such as permanent node departures, hardware failures, and accidental deletions. In order to maintain data availability, it is necessary to regenerate new redundant data in another node, referred to as a newcomer. Regeneration is expected to be finished as soon as possible, because the regeneration time can influence the data reliability and availability of distributed storage systems. It has been acknowledged that linear network coding can regenerate redundant data with less network traffic than replica and erasure codes. However, previous regeneration schemes are all star-structured regeneration schemes, in which data are transferred directly from existing storage nodes, referred to as providers, to the newcomer, so the regeneration time is always limited by the path with the narrowest bandwidth between newcomer and provider, due to bandwidth heterogeneity. In this paper, we exploit the bandwidth between providers and propose a tree-structured regeneration scheme using linear network coding. In our scheme, data can be transferred from providers to the newcomer through a regeneration tree, defined as a spanning tree covering the newcomer and all the providers. In a regeneration tree, a provider can receive data from other providers, then encode the received data with the data this provider stores, and finally send the encoded data to another provider or to the newcomer. We prove that a maximum spanning tree is an optimal regeneration tree and analyze its performance. In a trace-based simulation, the results show the tree-structured scheme can reduce the regeneration time by 75%-82% and improve data availability by 73%-124%.

OLAP is supported by more and more environment as a powerful analysis tool. With the rapid development of mobile and wireless technologies, users wish to enjoy the OLAP service on these devices. However, there are many issues on mobile OLAP against the traditional ones, e.g. the transmission bottleneck, unstable network connection, etc. Moreover, the mobile device owners have raised increasing requirements to customize the service such as transmitting the data on demand or ASAP to support their activities. All these challenges provide new chances for OLAP. In this paper, a new mechanism Gradual Cube is proposed to face such challenges. It can reduce the transmission data size, provide customized transmission strategy and enable users to conduct off-line browsing. We assume the users' precision requirement follows some distribution so that three methods, namely random, optimal and heuristic, are developed to customize the transmission plan. The experiments show that such methods are both effective and efficient.