Maximum Distance Profile (MDP) convolutional codes are an important class of channel codes due to their maximal delay-constrained error correction capabilities. The design of MDP codes has attracted significant attention from the research community. However, only limited attention was given to addressing the complexity of encoding and decoding operations. This paper aims to reduce encoding complexity by constructing partial unit-memory MDP codes with structured and sparse generator matrices. In particular, we present a matrix completion framework that extends a structured superregular matrix (e.g., Cauchy) over a small field to a sparse sliding generator matrix of an MDP code. We show that the proposed construction can reduce the encoding complexity compared to the current state-of-the-art MDP code designs.

We study a Faulty Congested Clique model, in which an adversary may fail nodes in the network throughout the computation. We show that any task of $O(n\log{n})$-bit input per node can be solved in roughly $n$ rounds, where $n$ is the size of the network. This nearly matches the linear upper bound on the complexity of the non-faulty Congested Clique model for such problems, by learning the entire input, and it holds in the faulty model even with a linear number of faults. Our main contribution is that we establish that one can do much better by looking more closely at the computation. Given a deterministic algorithm $\mathcal{A}$ for the non-faulty Congested Clique model, we show how to transform it into an algorithm $\mathcal{A}'$ for the faulty model, with an overhead that could be as small as some logarithmic-in-$n$ factor, by considering refined complexity measures of $\mathcal{A}$. As an exemplifying application of our approach, we show that the $O(n^{1/3})$-round complexity of semi-ring matrix multiplication [Censor-Hillel, Kaski, Korhonen, Lenzen, Paz, Suomela, PODC 2015] remains the same up to polylog factors in the faulty model, even if the adversary can fail $99\%$ of the nodes (or any other constant fraction).

Symbolic computation for systems of differential equations is often computationally expensive. Many practical differential models have a form of polynomial or rational ODE system with specified outputs. A basic symbolic approach to analyze these models is to compute and then symbolically process the polynomial system obtained by sufficiently many Lie derivatives of the output functions with respect to the vector field given by the ODE system.

We extend coded distributed computing over finite fields to allow the number of workers to be larger than the field size. We give codes that work for fully general matrix multiplication and show that in this case we serendipitously have that all functions can be computed in a distributed fault-tolerant fashion over finite fields. This generalizes previous results on the topic. We prove that the associated codes achieve a recovery threshold similar to the ones for characteristic zero fields but now with a factor that is proportional to the genus of the underlying function field. In particular, we have that the recovery threshold of these codes is proportional to the classical complexity of matrix multiplication by a factor of at most the genus.

Tensors are a fundamental operation in distributed computing, e.g., machine learning, that are commonly distributed into multiple parallel tasks for large datasets. Stragglers and other failures can severely impact the overall completion time. Recent works in coded computing provide a novel strategy to mitigate stragglers with coded tasks, with an objective of minimizing the number of tasks needed to recover the overall result, known as the recovery threshold. However, we demonstrate that this strict combinatorial definition does not directly optimize the probability of failure. In this paper, we focus on the most likely event and measure the optimality of a coding scheme more directly by its probability of decoding. Our probabilistic approach leads us to a practical construction of random codes for matrix multiplication, i.e., locally random alloy codes, which are optimal with respect to the measures. Furthermore, the probabilistic approach allows us to discover a surprising impossibility theorem about both random and deterministic coded distributed tensors.

Fault tolerance is a major concern in distributed computational settings. In the classic master-worker setting, a server (the master) needs to perform some heavy computation which it may distribute to m other machines (workers) in order to speed up the time complexity. In this setting, it is crucial that the computation is made robust to failed workers, in order for the master to be able to retrieve the result of the joint computation despite failures. A prime complexity measure is thus the recovery threshold, which is the number of workers that the master needs to wait for in order to derive the output. This is the counterpart to the number of failed workers that it can tolerate. In this paper, we address the fundamental and well-studied task of matrix multiplication. Specifically, our focus is on when the master needs to multiply a batch of n pairs of matrices. Several coding techniques have been proven successful in reducing the recovery threshold for this task, and one approach that is also very efficient in terms of computation time is called Rook Codes. The previously best known recovery threshold for batch matrix multiplication using Rook Codes is $$O(n^{\log _2{3}})=O(n^{1.585})$$ . Our main contribution is a lower bound proof that says that any Rook Code for batch matrix multiplication must have a recovery threshold that is at least $$\omega (n)$$ . Notably, we employ techniques from Additive Combinatorics in order to prove this, which may be of further interest. Moreover, we show a Rook Code that achieves a recovery threshold of $$n^{1+o(1)}$$ , establishing a near-optimal answer to the fault tolerance of this coding scheme.

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.

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

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.

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.