Campus Units

Electrical and Computer Engineering, Mathematics

Document Type

Article

Publication Version

Submitted Manuscript

Publication Date

2018

Journal or Book Title

arXiv

Abstract

In distributed computing systems, it is well recognized that worker nodes that are slow (called stragglers) tend to dominate the overall job execution time. Coded computation utilizes concepts from erasure coding to mitigate the effect of stragglers by running "coded" copies of tasks comprising a job. Stragglers are typically treated as erasures in this process. While this is useful, there are issues with applying, e.g., MDS codes in a straightforward manner. Specifically, several applications such as matrix-vector products deal with sparse matrices. MDS codes typically require dense linear combinations of submatrices of the original matrix which destroy their inherent sparsity. This is problematic as it results in significantly higher processing times for computing the submatrix-vector products in coded computation. Furthermore, it also ignores partial computations at stragglers.
In this work, we propose a fine-grained model that quantifies the level of non-trivial coding needed to obtain the benefits of coding in matrix-vector computation. Simultaneously, it allows us to leverage partial computations performed by the straggler nodes. For this model, we propose and evaluate several code designs and discuss their properties.

Comments

This is a pre-print of the article Das, Anindya B., Li Tang, and Aditya Ramamoorthy. "C3LES: Codes for Coded Computation that Leverage Stragglers." arXiv preprint arXiv:1809.06242 (2018). Posted with permission.

Copyright Owner

The Authors

Language

en

File Format

application/pdf

Published Version

Share

COinS