Block-Diagonal and LT Codes for Distributed Computing With Straggling Servers
Top Cited Papers
- 22 October 2018
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Communications
- Vol. 67 (3) , 1739-1753
Abstract
We propose two coded schemes for the distributed computing problem of multiplying a matrix by a set of vectors. The first scheme is based on partitioning the matrix into submatrices and applying maximum distance separable (MDS) codes to each submatrix. For this scheme, we prove that up to a given number of partitions the communication load and the computational delay (not including the encoding and decoding delay) are identical to those of the scheme recently proposed by Li et al., based on a single, long MDS code. However, due to the use of shorter MDS codes, our scheme yields a significantly lower overall computational delay when the delay incurred by encoding and decoding is also considered. We further propose a second coded scheme based on Luby Transform (LT) codes under inactivation decoding. Interestingly, LT codes may reduce the delay over the partitioned scheme at the expense of an increased communication load. We also consider distributed computing under a deadline and show numerically that the proposed schemes outperform other schemes in the literature, with the LT code-based scheme yielding the best performance for the scenarios considered.Keywords
All Related Versions
Funding Information
- Vetenskapsrådet (2016-04253)
- Norges Forskningsråd (240985/F20)
This publication has 24 references indexed in Scilit:
- Using Straggler Replication to Reduce Latency in Large-scale Parallel ComputingACM SIGMETRICS Performance Evaluation Review, 2015
- Coded MapReduce2015
- Large-scale cluster management at Google with Borg2015
- Data-intensive applications, challenges, techniques and technologies: A survey on Big DataInformation Sciences, 2014
- Streaming Big Data Processing in Datacenter CloudsIEEE Cloud Computing, 2014
- The PageRank Problem, Multiagent Consensus, and Web Aggregation: A Systems and Control ViewpointIEEE Control Systems, 2014
- TOFEC: Achieving optimal throughput-delay trade-off of cloud storage using erasure codes2014
- The Datacenter as a Computer: An Introduction to the Design of Warehouse-Scale MachinesSynthesis Lectures on Computer Architecture, 2009
- LT codes2003
- An efficient method for finding the minimum of a function of several variables without calculating derivativesThe Computer Journal, 1964