Straggler-Resilient and Communication-Efficient Distributed Iterative Linear Solver

Abstract

We propose a novel distributed iterative linear inverse solver method. Our method, PolyLin, has significantly lower communication cost, both in terms of number of rounds as well as number of bits, in comparison with the state of the art at the cost of higher computational complexity and storage. Our algorithm also has a built-in resilience to straggling and faulty computation nodes. We develop a natural variant of our main algorithm that trades off communication cost for computational complexity. Our method is inspired by ideas in error correcting codes.

arXiv comment15 pages, 3 figures and 2 tables

References in corpus (6)

• Speeding Up Distributed Machine Learning Using Codes
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication
• Communication-Computation Efficient Gradient Coding
• Approximate Gradient Coding via Sparse Random Graphs
• Robust Gradient Descent via Moment Encoding with LDPC Codes

Cited by in corpus (5)

• Straggler-aware Distributed Learning: Communication Computation Latency Trade-off
• A Survey of Coded Distributed Computing
• CodeNet: Training Large Scale Neural Networks in Presence of Soft-Errors
• Recycled ADMM: Improve Privacy and Accuracy with Less Computation in Distributed Algorithms
• Coded Elastic Computing