Using Straggler Replication to Reduce Latency in Large-scale Parallel Computing

By Da Wang, Gauri Joshi, Gregory W. Wornell. 2015

139 citations recorded by the source corpus.

In cloud computing jobs consisting of many tasks run in parallel, the tasks on the slowest machines (straggling tasks) become the bottleneck in the completion of the job. One way to combat the variability in machine response time is to add replicas of straggling tasks and wait for the earliest copy to finish. Using the theory of extreme order statistics, we analyze how task replication reduces latency, and its impact on the cost of computing resources. We also propose a heuristic algorithm to search for the best replication strategies when it is difficult to model the empirical behavior of task execution time and use the proposed analysis techniques. Evaluation of the heuristic policies on Google Trace data shows a significant latency reduction compared to the replication strategy used in MapReduce.

Subfields: Computer Networks and Communications, Information Systems, Management Information Systems

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Information Systems

In Management Information Systems

Citations in the corpus

Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGD (2018, neutral): “An alternate direction of work is to use redundancy techniques as proposed in [Dutta et al., 2016, Lee et al., 2017, Tandon et al., 2017, Wang et al., 2015] to ignore the stragglers altogether.”
“Short-Dot”: Computing Large Linear Transforms Distributedly Using Coded Short Dot Products (2017, background): “Erasure codes are often found to offer advantages over replication (the latter is analyzed in [3]–[5]).”
Straggler Mitigation in Distributed Optimization Through Data Encoding (2017, methodology): “Use of data replication to aid with the straggler problem has been proposed and studied in [22, 1], and references therein.”
Rateless codes for near-perfect load balancing in distributed matrix-vector multiplication (2018, background): “A natural approach to countering stragglers involves replicating individual tasks at multiple worker nodes [7]–[10], and waiting for any one copy to finish.”
Queues with Redundancy: Latency-Cost Analysis (2015, background): “General service time distribution, in particular the effect of its tail, is considered in [7, 8].”
Coded convolution for parallel and distributed computing within a deadline (2017, background): “The use of replication [8], [9] is a natural strategy for dealing with stragglers in distributed systems since the computation only requires a subset of the processors to finish.”
Distributed and Private Coded Matrix Computation with Flexible Communication Load (2019, background): “computing tasks [4], recent work has shown that encoding the input data can help reduce the computation latency, which depends on the number of tolerated stragglers by orders of magnitude, e.g., [5], [6]. More generally, coding is able to control the tradeoff between computational delay and communic”
Redundancy Techniques for Straggler Mitigation in Distributed Optimization and Learning (2018, background): “Such techniques have been proposed and analyzed in Gardner et al. (2015); Ananthanarayanan et al. (2013); Shah et al. (2016); Wang et al. (2015); Yadwadkar et al. (2016), among others.”
Coded computation over heterogeneous clusters (2017, background): “Addressing stragglers has attracted a lot of attention in the queuing-based frameworks for large-scale computation as well [30], [31].”
Coded Computation Over Heterogeneous Clusters (2019, background): “Addressing stragglers has attracted a lot of attention in the queuing-based frameworks for large-scale computation as well [30], [31].”
Secure Distributed Computing With Straggling Servers Using Polynomial Codes (2019, background): “, straggling effect, is to allow redundancies when assigning tasks to the workers [2].”