Efficient task replication for fast response times in parallel computation

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

125 citations recorded by the source corpus.

Large-scale distributed computing systems divide a job into many independent tasks and run them in parallel on different machines. A challenge in such parallel computing is that the time taken by a machine to execute a task is inherently variable, and thus the slowest machine becomes the bottleneck in the completion of the job. One way to combat the variability in machine response is to replicate tasks on multiple machines and waiting for the machine that finishes first. While task replication reduces response time, it generally increases resource usage. In this work, we propose a theoretical framework to analyze the trade-off between response time and resource usage. Given an execution time distribution for machines, our analysis gives insights on when and why replication helps. We also propose efficient scheduling algorithms for large-scale distributed computing systems.

Subfields: Computer Networks and Communications, Hardware and Architecture, 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 Hardware and Architecture

In Information Systems

Citations in the corpus

Robust and Communication-Efficient Collaborative Learning (2019, background): “A common approach to mitigate stragglers is to replicate the computing task of the slow nodes to other computing nodes (Ananthanarayanan et al., 2013; Wang et al., 2014), but this is clearly not feasible in collaborative learning.”
Speeding Up Distributed Machine Learning Using Codes (2015, neutral): “D C ] 2 9 Ja n 20 18 2 input data dist. store aggregate function Communication graph storage phase communication phase computation phase 1 2 3 1 2 3 Fig.”
“Short-Dot”: Computing Large Linear Transforms Distributedly Using Coded Short Dot Products (2017, methodology): “To address this problem, we provide techniques (building on [1] [2] [3] [4] [5]) that introduce redundancy in the computation by designing a novel error-correction mechanism that allows the size of individual dot products computed at each processor to be shorter than the length of the input.”
Approximate Gradient Coding via Sparse Random Graphs (2017, background): “These approaches include replicating jobs across redundant nodes [22] and dropping stragglers in the case that the underlying computation is robust to errors [1, 24].”
Using Straggler Replication to Reduce Latency in Large-scale Parallel Computing (2015, background): “Replication strategies are analyzed in [11], mainly for the single task case.”
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.”
Rateless codes for near-perfect load balancing in distributed matrix-vector multiplication (2018, background): “This strategy of task replication has many variants such as [7], [8], and has been theoretically analyzed in [9] and [10] where schemes for adding redundant copies based on the tail of the runtime distribution at the workers are proposed.”