Search

Computing systems are evolving rapidly. At the device level, emerging devices are beginning to compete with traditional CMOS systems. At the architecture level, novel architectures are successfully avoiding the communication bottleneck that is a central feature, and a central limitation, of the von Neumann architecture. Furthermore, such systems are increasingly plagued by unreliability. This unreliability arises at device or gate-level in emerging devices, and can percolate up to processor or system-level if left unchecked. The goal of this article is to survey recent advances in reliable computing using unreliable elements, with an eye on nonsilicon and non-von Neumann architectures. We first observe that instead of aiming for generic computing problems, the community could use “dwarfs of modern computing,” first noted in the high-performance computing (HPC) community, as a starting point. These computing problems are the basic building blocks of almost all scientific computing, machine learning, and data analytics today. Next, we survey the state of the art in “coded computing,” which is an emerging area that advances on classical algorithm-based fault-tolerance (ABFT) and brings a fundamental information-theoretic perspective. By weaving error-correcting codes into a computing algorithm, coded computing provides dramatic improvements on solutions, as well as obtains novel fundamental limits, for problems that have been open for more than 30 years. We introduce existing and novel coded computing techniques in the context of “coded dwarfs,” where a specific dwarf’s computation is made resilient by applying coding. We discuss how, for the same redundancy, “coded dwarfs” are significantly more resilient compared to classical techniques such as replication. Furthermore, by examining a widely popular computation task—training large neural networks—we demonstrate how coded dwarfs can be applied to address this fundamentally nonlinear problem. Finally, we discuss practical challenges and future directions in implementing coded computing techniques on emerging and existing nonsilicon and/or non-von Neumann architectures.

We provide novel coded computation strategies for distributed matrix-matrix products that outperform the recent "Polynomial code" constructions in recovery threshold, i.e., the required number of successful workers. When $m$-th fraction of each matrix can be stored in each worker node, Polynomial codes require $m^2$ successful workers, while our MatDot codes only require $2m-1$ successful workers, albeit at a higher communication cost from each worker to the fusion node. We also provide a systematic construction of MatDot codes. Further, we propose "PolyDot" coding that interpolates between Polynomial codes and MatDot codes to trade off communication cost and recovery threshold. Finally, we demonstrate a coding technique for multiplying $n$ matrices ($n \geq 3$) by applying MatDot and PolyDot coding ideas., Comment: Extended version of the paper that appeared at Allerton 2017 (October 2017), including full proofs and further results. Submitted to IEEE Transactions on Information Theory

Faced with saturation of Moore's law and increasing dimension of data, system designers have increasingly resorted to parallel and distributed computing. However, distributed computing is often bottle necked by a small fraction of slow processors called "stragglers" that reduce the speed of computation because the fusion node has to wait for all processors to finish. To combat the effect of stragglers, recent literature introduces redundancy in computations across processors, e.g.,~using repetition-based strategies or erasure codes. The fusion node can exploit this redundancy by completing the computation using outputs from only a subset of the processors, ignoring the stragglers. In this paper, we propose a novel technique -- that we call "Short-Dot" -- to introduce redundant computations in a coding theory inspired fashion, for computing linear transforms of long vectors. Instead of computing long dot products as required in the original linear transform, we construct a larger number of redundant and short dot products that can be computed faster and more efficiently at individual processors. In reference to comparable schemes that introduce redundancy to tackle stragglers, Short-Dot reduces the cost of computation, storage and communication since shorter portions are stored and computed at each processor, and also shorter portions of the input is communicated to each processor. We demonstrate through probabilistic analysis as well as experiments that Short-Dot offers significant speed-up compared to existing techniques. We also derive trade-offs between the length of the dot-products and the resilience to stragglers (number of processors to wait for), for any such strategy and compare it to that achieved by our strategy., Comment: Presented at NIPS 2016, Barcelona, Spain

In this work, we propose an erasure coding-based protocol that implements a key-value store with atomicity and near-optimal storage cost. Our protocol supports concurrent read and write operations while tolerating asynchronous communication and crash failures of any client and some fraction of servers. One novel feature is a tunable knob between the number of supported concurrent operations, availability, and storage cost. We implement our protocol into Cassandra, namely Cassan-drEAS (Cassandra + Erasure-coding Atomic Storage). Extensive evaluation using YCSB on Google Cloud Platform shows that CassandrEAS incurs moderate penalty on latency and throughput, yet saves significant amount of storage space.

In applications of distributed storage systems to modern key-value stores, the stored data is highly dynamic due to frequent updates. The multi-version coding problem was formulated to study the cost of storing dynamic data in distributed storage systems. Previous work on multi-version coding considered a completely decentralized and asynchronous system assuming that the servers are not aware of which versions of the data are received by the other servers. In this paper, we relax this assumption and study a system where a server may acquire side information of the data versions propagated to some other servers based on the network topology. Specifically, we study a storage system with $n$ servers over a directed graph that store $\nu$ totally ordered versions of a message. Each server receives a subset of these $\nu$ versions. A server is aware of which versions have been received by its neighbors in the network graph. We show that the side information can result in a better storage cost as compared with the case where there is no side information for some regimes at the expense of the additional latency associated with exchanging the side information. Through an information-theoretic converse, we identify surprising scenarios where the side information may not help in improving the worst-case storage cost beyond the case where servers have no side information. Finally, we present a case study over Amazon web services (AWS) that demonstrates the potential cost reductions that may be obtained by our constructions., Comment: Extended version of the ISIT 2018 paper that generalizes the code constructions and converse for arbitrary graphs, and a case study based on Amazon web services pricing and latency information

In this paper, we propose a novel fault-tolerant parallel matrix multiplication algorithm called 3D Coded SUMMA that achieves higher failure-tolerance than replication-based schemes for the same amount of redundancy. This work bridges the gap between recent developments in coded computing and fault-tolerance in high-performance computing (HPC). The core idea of coded computing is the same as algorithm-based fault-tolerance (ABFT), which is weaving redundancy in the computation using error-correcting codes. In particular, we show that MatDot codes, an innovative code construction for parallel matrix multiplications, can be integrated into three-dimensional SUMMA (Scalable Universal Matrix Multiplication Algorithm [30]) in a communication-avoiding manner. To tolerate any two node failures, the proposed 3D Coded SUMMA requires \(\sim \)50% less redundancy than replication, while the overhead in execution time is only about 5–10%.

In applications of distributed storage systems to distributed computing and implementation of key-value stores, the following property, usually referred to as consistency in distributed computing, is an important requirement: as the data stored changes, the latest version of the data must be accessible to a client that connects to the storage system. Motivated by technological trends where key-value stores are increasingly implemented in high-speed memory, an information theoretic formulation called multi-version coding is introduced in this paper in order to understand and minimize the memory overhead of consistent distributed storage. Multi-version coding is characterized by $\nu$ totally ordered versions of a message and a storage system with $n$ servers. At each server, values corresponding to an arbitrary subset of the $\nu$ versions are received and encoded. For any subset of $c$ servers in the storage system, the value corresponding to the latest common version or a later version, as per the total ordering, among the $c$ servers is required to be decodable. An achievable multi-version code construction via linear coding and a converse result that shows that the construction is asymptotically tight when $\nu |(c-1)$ are provided. An implication of the converse is that there is an inevitable price, in terms of storage cost, to ensure consistency in distributed storage systems.

In this paper, we propose a distributed coding scheme that allows for lower computation cost per computing node than the standard Lagrange Coded Computing scheme. The proposed coding scheme is useful for cases where the elements of the input data set are of large dimensions and the computing nodes have limited computation power. This coding scheme provides a trade-off between the computation cost per worker and the recovery threshold in a distributed coded computing framework. The proposed scheme is also extended to provide data privacy against at most t colluding worker nodes in the system.

We study the numerical stability of polynomial based encoding methods, which has emerged to be a powerful class of techniques for providing straggler and fault tolerance in the area of coded computing. Our contributions are as follows: 1) We construct new codes for matrix multiplication that achieve the same fault/straggler tolerance as the previously constructed MatDot Codes and Polynomial Codes. Unlike previous codes that use polynomials expanded in a monomial basis, our codes uses a basis of orthogonal polynomials. 2) We show that the condition number of every $m \times m$ sub-matrix of an $m \times n, n \geq m$ Chebyshev-Vandermonde matrix, evaluated on the $n$-point Chebyshev grid, grows as $O(n^{2(n-m)})$ for $n > m$. An implication of this result is that, when Chebyshev-Vandermonde matrices are used for coded computing, for a fixed number of redundant nodes $s=n-m,$ the condition number grows at most polynomially in the number of nodes $n$. 3) By specializing our orthogonal polynomial based constructions to Chebyshev polynomials, and using our condition number bound for Chebyshev-Vandermonde matrices, we construct new numerically stable techniques for coded matrix multiplication. We empirically demonstrate that our constructions have significantly lower numerical errors compared to previous approaches which involve inversion of Vandermonde matrices. We generalize our constructions to explore the trade-off between computation/communication and fault-tolerance. 4) We propose a numerically stable specialization of Lagrange coded computing. Motivated by our condition number bound, our approach involves the choice of evaluation points and a suitable decoding procedure that involves inversion of an appropriate Chebyshev-Vandermonde matrix. Our approach is demonstrated empirically to have lower numerical errors as compared to standard methods., 31 pages, 13 figures, to be presented in part at the IEEE International Symposium on Information Theory (ISIT), July 2019

© 2019 IEEE. Emulating a shared atomic, read/write storage system is a fundamental problem in distributed computing. Replicating atomic objects among a set of data hosts was the norm for traditional implementations (e.g., [6]) in order to guarantee the availability and accessibility of the data despite host failures. As replication is highly storage demanding, recent approaches suggested the use of erasure-codes to offer the same fault-tolerance while optimizing storage usage at the hosts. Initial works focused on a fix set of data hosts. To guarantee longevity and scalability, a storage service should be able to dynamically mask hosts failures by allowing new hosts to join, and failed host to be removed without service interruptions. This work presents the first erasure-code based atomic algorithm, called ARES, which allows the set of hosts to be modified in the course of an execution. ARES is composed of three main components: (i) a reconfiguration protocol, (ii) a read/write protocol, and (iii) a set of data access primitives. The design of ARES is modular and is such to accommodate the usage of various erasure-code parameters on a per-configuration basis. We provide bounds on the latency of read/write operations and analyze the storage and communication costs of the ARES algorithm.

We introduce the idea of cross-iteration coded computing, an approach to reducing communication costs for a large class of distributed iterative algorithms involving linear operations, including gradient descent and accelerated gradient descent for quadratic loss functions. The state-of-the-art approach for these iterative algorithms involves performing one iteration of the algorithm per round of communication among the nodes. In contrast, our approach performs multiple iterations of the underlying algorithm in a single round of communication by incorporating some redundancy storage and computation. Our algorithm works in the master-worker setting with the workers storing carefully constructed linear transformations of input matrices and using these matrices in an iterative algorithm, with the master node inverting the effect of these linear transformations. In addition to reduced communication costs, a trivial generalization of our algorithm also includes resilience to stragglers and failures. The degree of redundancy of our algorithm can be tuned based on the amount of communication and straggler resilience required. Finally, we also describe a variant of our algorithm that can flexibly recover the results based on the degree of straggling in the worker nodes. The variant allows for the performance to degrade gracefully as the number of successful (non-straggling) workers is lowered.

Recent work has developed coding theoretic approaches to add redundancy to distributed matrix-vector multiplications with the goal of speeding up the computation by mitigating the straggler effect in distributed computing. In this paper, we consider the case where the matrix comes from a small (e.g., binary) alphabet, where a variant of a popular method called the “Four-Russians method” is known to have significantly lower computational complexity as compared with the usual matrix-vector multiplication algorithm. We develop novel code constructions that are applicable to binary matrix-vector multiplication via a variant of the Four-Russians method called the Mailman algorithm. Specifically, in our constructions, the encoded matrices have a low alphabet that ensures lower computational complexity, as well as good straggler tolerance. We also present a trade-off between the communication and computation cost of distributed coded matrix-vector multiplication for general, possibly non-binary, matrices.

We consider the problem of computing the convolution of two long vectors using parallel processing units in the presence of "stragglers". Stragglers refer to the small fraction of faulty or slow processors that delays the entire computation in time-critical distributed systems. We first show that splitting the vectors into smaller pieces and using a linear code to encode these pieces provides better resilience against stragglers than replication-based schemes under a simple, worst-case straggler analysis. We then demonstrate that under commonly used models of computation time, coding can dramatically improve the probability of finishing the computation within a target "deadline" time. As opposed to the more commonly used technique of expected computation time analysis, we quantify the exponents of the probability of failure in the limit of large deadlines. Our exponent metric captures the probability of failing to finish before a specified deadline time, i.e. , the behavior of the "tail". Moreover, our technique also allows for simple closed form expressions for more general models of computation time, e.g. shifted Weibull models instead of only shifted exponentials. Thus, through this problem of coded convolution, we establish the utility of a novel asymptotic failure exponent analysis for distributed systems., Comment: To appear in ISIT 2017

Motivated by applications of distributed storage systems to key-value stores, recently, the multi-version coding problem was proposed to store data that is frequently being updated in a distributed storage system. In particular, in multi-version coding, it is desired to store the data consistently, that is, even if all servers do not receive the data updates simultaneously, the decoder can recover the latest possible version of the data. In this paper, we consider the case where there are correlations among various versions of the data. By respectively leveraging update-efficient codes and Slepian-Wolf, we provide two simple multi-version code constructions to show that the storage cost of multi-version codes can be significantly smaller than previous constructions depending on the degree of correlation between the versions. Moreover, we show that our Slepian-Wolf based construction is essentially optimal in a certain correlation regime.

© 2016 ACM. The focus of this paper is to understand storage costs of em- ulating an atomic shared memory over an asynchronous, dis- tributed message passing system. Previous literature has de- veloped several shared memory emulation algorithms based on replication and erasure coding techniques, and analyzed the storage costs of the proposed algorithms. In this pa- per, we present the first known information-theoretic lower bounds on the storage costs incurred by shared memory em- ulation algorithms. Our storage cost lower bounds are uni- versally applicable, that is, we make no assumption on the structure of the algorithm or the method of encoding the data. We consider an arbitrary algorithm A that implements an atomic multi-writer-single-reader (MWSR) shared memory variable whose values come from a finite set V over a system of N servers connected by point-to-point asynchronous links. We require that in every fair execution of algorithm A where the number of server failures is smaller than a parameter f, every operation invoked at a non-failing client terminates. We define the storage cost of a server in algorithm A as the logarithm (to base 2) of the number of states it can take on; the total storage cost of algorithm A is the sum of the storage cost of all servers. Previously, it was known that the storage cost cannot be smaller than N/N-f log2 |V|. We develop three new lower bounds on the storage cost of algorithm A. • In our first lower bound, we show that if algorithm A does not use server gossip, then the total storage cost is lower bounded by 2N/N-f+1 log2 |V| - o(log2 |V|). • In our second lower bound we show that the total stor- age cost is at least 2N/N-f+2 log2 |V| - o(log2 |V|) even if the algorithm uses server gossip. • In our third lower bound, we consider algorithms where the write protocol sends information about the value in at most one phase. For such algorithms, we show that the total storage cost is at least v∗ N/N-f+v∗-1 log2(|V|) -o(log2(|V|), where v∗ is the minimum of f + 1 and the number of active write operations of an execution. Our first and second lower bounds are approximately twice as strong as the previously known bound of N/N-f log2 |V|. Furthermore, our first two lower bounds apply even for regu- lar, single-writer-single-reader (SWSR) shared memory em- ulation algorithms. Our third lower bound is much larger than our first and second lower bounds, although it is appli- cable to a smaller class of algorithms where the write proto- col has certain restrictions. In particular, our third bound is comparable to the storage cost achieved by most shared memory emulation algorithms in the literature, which nat- urally fall under the class of algorithms studied. Our proof ideas are inspired by recent results in coding theory.

The compute-and-forward framework permits each receiver in a Gaussian network to directly decode a linear combination of the transmitted messages. The resulting linear combinations can then be employed as an end-to-end communication strategy for relaying, interference alignment, and other applications. Recent efforts have demonstrated the advantages of employing unequal powers at the transmitters and decoding more than one linear combination at each receiver. However, neither of these techniques fit naturally within the original formulation of compute-and-forward. This paper proposes an expanded compute-and-forward framework that incorporates both of these possibilities and permits an intuitive interpretation in terms of signal levels. Within this framework, recent achievability and optimality results are unified and generalized., 30 pages, 10 figures, to appear in IEEE Transactions on Information Theory

A client/encoder edits a file, as modeled by an insertion-deletion (InDel) process. An old copy of the file is stored remotely at a data-centre/decoder, and is also available to the client. We consider the problem of throughput- and computationally-efficient communication from the client to the data-centre, to enable the server to update its copy to the newly edited file. We study two models for the source files/edit patterns: the random pre-edit sequence left-to-right random InDel (RPES-LtRRID) process, and the arbitrary pre-edit sequence arbitrary InDel (APES-AID) process. In both models, we consider the regime in which the number of insertions/deletions is a small (but constant) fraction of the original file. For both models we prove information-theoretic lower bounds on the best possible compression rates that enable file updates. Conversely, our compression algorithms use dynamic programming (DP) and entropy coding, and achieve rates that are approximately optimal., The paper is an extended version of our paper to be appeared at ITW 2015

This paper considers the communication and storage costs of emulating atomic (linearizable) multi-writer multi-reader shared memory in distributed message-passing systems. The paper contains two main contributions: 1) We present an atomic shared-memory emulation algorithm that we call Coded Atomic Storage (CAS). This algorithm uses erasure coding methods. In a storage system with 'N' servers that is resilient to 'f' server failures, we show that the communication cost of CAS is N/(N-2f). The storage cost of CAS is unbounded. 2) We present a variant of CAS known as CAS with Garbage Collection (CASGC). The CASGC algorithm is parametrized by an integer 'd' and has a bounded storage cost. We show that in every execution where the number of write operations that are concurrent with a read operation is no bigger than d, the CASGC algorithm with parameter d satisfies atomicity and liveness. We explicitly characterize the storage cost of CASGC, and show that it has the same communication cost as CAS., United States. Air Force Office of Scientific Research (Contract FA9550-13-1-0042), National Science Foundation (U.S.) (Award CCF-1217506), National Science Foundation (U.S.) (Award 0939370-CCF), BAE Systems National Security Solutions Inc. (Award 739532-SLIN 0004)

The index coding problem is studied from an interference alignment perspective providing new results as well as new insights into, and generalizations of, previously known results. An equivalence is established between the capacity of multiple unicast index coding (where each message is desired by exactly one receiver), and groupcast index coding (where a message can be desired by multiple receivers), which settles the heretofore open question of insufficiency of linear codes for the multiple unicast index coding problem by equivalence with groupcast settings, where this question has previously been answered. Necessary and sufficient conditions for the achievability of rate half per message in the index coding problem are shown to be a natural consequence of interference alignment constraints, and generalizations to feasibility of rate 1/(L+1)per message when each destination desires at least L messages, are similarly obtained. Finally, capacity optimal solutions are presented to a series of symmetric index coding problems inspired by the local connectivity and local interference characteristics of wireless networks. The solutions are based on vector linear coding. © 1963-2012 IEEE.