Straggler Mitigation with Tiered Gradient Codes

Abstract

Coding theoretic techniques have been proposed for synchronous Gradient Descent (GD) on multiple servers to mitigate stragglers. These techniques provide the flexibility that the job is complete when any $k$ out of $n$ servers finish their assigned tasks. The task size on each server is found based on the values of $k$ and $n$. However, it is assumed that all the $n$ jobs are started when the job is requested. In contrast, we assume a tiered system, where we start with $n_1\ge k$ tasks, and on completion of $c$ tasks, we start $n_2-n_1$ more tasks. The aim is that as long as $k$ servers can execute their tasks, the job gets completed. This paper exploits the flexibility that not all servers are started at the request time to obtain the achievable task sizes on each server. The task sizes are in general lower than starting all $n_2$ tasks at the request times thus helping achieve lower task sizes which helps to reduce both the job completion time and the total server utilization.

30 pages, 6 figures and 2 tables

References in corpus (8)

• Speeding Up Distributed Machine Learning Using Codes
• Communication-Computation Efficient Gradient Coding
• When Queueing Meets Coding: Optimal-Latency Data Retrieving Scheme in Storage Clouds
• Joint Latency and Cost Optimization for Erasure-coded Data Center Storage
• ErasureHead: Distributed Gradient Descent without Delays Using Approximate Gradient Coding
• Optimal Server Selection for Straggler Mitigation
• Taming Tail Latency for Erasure-coded, Distributed Storage Systems
• Gradient Coding via the Stochastic Block Model

Cited by in corpus (2)

• Straggler-aware Distributed Learning: Communication Computation Latency Trade-off
• Grand Challenges in Resilience: Autonomous System Resilience through Design and Runtime Measures