Diversity/Parallelism Trade-off in Distributed Systems with Redundancy

Abstract

As numerous machine learning and other algorithms increase in complexity and data requirements, distributed computing becomes necessary to satisfy the growing computational and storage demands, because it enables parallel execution of smaller tasks that make up a large computing job. However, random fluctuations in task service times lead to straggling tasks with long execution times. Redundancy, in the form of task replication and erasure coding, provides diversity that allows a job to be completed when only a subset of redundant tasks is executed, thus removing the dependency on the straggling tasks. In situations of constrained resources (here a fixed number of parallel servers), increasing redundancy reduces the available resources for parallelism. In this paper, we characterize the diversity vs. parallelism trade-off and identify the optimal strategy, among replication, coding and splitting, which minimizes the expected job completion time. We consider three common service time distributions and establish three models that describe scaling of these distributions with the task size. We find that different distributions with different scaling models operate optimally at different levels of redundancy, and thus may require very different code rates.

arXiv commentTwo columns version, corrected typos

References in corpus (12)

• TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems
• One weird trick for parallelizing convolutional neural networks
• Speeding Up Distributed Machine Learning Using Codes
• Revisiting Distributed Synchronous SGD
• Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication
• Communication-Computation Efficient Gradient Coding
• High-Performance Distributed ML at Scale through Parameter Server Consistency Models
• Minimizing Latency for Secure Coded Computing Using Secret Sharing via Staircase Codes
• Redundancy Techniques for Straggler Mitigation in Distributed Optimization and Learning
• Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGD
• Optimizing Redundancy Levels in Master-Worker Compute Clusters for Straggler Mitigation
• Redundancy Scheduling in Systems with Bi-Modal Job Service Time Distribution

Cited by in corpus (1)

• Efficient Replication for Straggler Mitigation in Distributed Computing