The tail at scale

By Joseph Dean, Luiz André Barroso. 2013

2,020 citations recorded by the source corpus.

Subfields: Computer Networks and Communications, Information Systems, ML Systems & Hardware

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 ML Systems & Hardware

Citations in the corpus

In-datacenter performance analysis of a tensor processing unit (2017, background): “• Four of the six NN apps are memory bound; if the TPU were revised to have the same memory as the K80 GPU, it would be about 30X – 50X faster than the GPU and CPU.”
Revisiting Distributed Synchronous SGD (2016, methodology): “To alleviate the straggler problem, we introduce backup workers (Dean & Barroso, 2013) as follows: instead of having only N workers, we add b extra workers, but as soon as the parameter servers receive gradients from any N workers, they stop waiting and update their parameters using the N gradients.”
Robust and Communication-Efficient Collaborative Learning (2019, background): “The straggler problem has been widely observed in distributed computing clusters (Dean and Barroso, 2013; Ananthanarayanan et al., 2010).”
Data Encoding for Byzantine-Resilient Distributed Optimization (2019, background): “There has been a significant recent interest in using codingtheoretic techniques to mitigate the well-known straggler problem [40], including gradient coding [43]–[46], encoding computation [33], [34], [47], and data encoding [41], [48].”
Staircase-PIR: Universally Robust Private Information Retrieval (2018, background): “The robustness property is motivated by the need to mitigate the effect of stragglers [3]–[11].”
Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGD (2018, neutral): “Random delays in computation (referred to as straggling) are common in today’s distributed systems [Dean and Barroso, 2013].”
Speeding Up Distributed Machine Learning Using Codes (2015, background): “Dean and Barroso [5] show that running a computational task at a computing node often involves unpredictable latency due to several factors such as network latency, shared resources, maintenance activities, and power limits.”
Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy (2018, background): “We then fix distinct {αi}(8)i=1 in F such that {αi}(8)i=1 ∩ [2] = ∅, and let workers 1, .”
Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication (2017, methodology): “As we scale out computations across many distributed nodes, a major performance bottleneck is the latency in waiting for slowest nodes, or “stragglers” to finish their tasks [3].”
“Short-Dot”: Computing Large Linear Transforms Distributedly Using Coded Short Dot Products (2017, background): “A common problem in distributed systems is “straggling” [10] where a few slow or faulty processing nodes (stragglers) can delay the entire computation.”
On the optimal recovery threshold of coded matrix multiplication (2017, neutral): “The issue of straggling [2] and faulty nodes has been a topic of active interest in the emerging area of “coded computation” with several interesting works, e.”
Hopper: Decentralized Speculation-aware Cluster Scheduling at Scale (2015, background): “Dealing with straggler tasks, i.e., tasks that take significantly longer than expected to complete, is an important challenge for cluster schedulers, one that was called out in the original MapReduce paper [24], and a topic of significant subsequent research [12, 14, 15, 50].”
When do redundant requests reduce latency ? (2013, background): “Dean and Barroso [8] observe a reduction in latency in Google’s system when requests are sent to two servers instead of one.”
Coded Computation Over Heterogeneous Clusters (2019, methodology): “To emulate the straggler effects in large-scale systems [36], we inject artificial delays.”
RDMA over Commodity Ethernet at Scale (2016, background): “Second, many modern DC applications like Search are highly latency sensitive [7, 15, 41].”
Using Straggler Replication to Reduce Latency in Large-scale Parallel Computing (2015, methodology): “Several algorithms used in optimization and machine learning, for example the Alter-nating Direction Method of Multipliers (ADMM) [4], and Markov Chain Monte-Carlo (MCMC) [14], fall into this class and can be parallelized easily.”
Heterogeneity-Aware Asynchronous Decentralized Training (2019, result): “The trend of heterogeneity and the “long tail effects” have been also discussed and confirmed in other recent works [5,12,24,28,35].”
A Unified Coded Deep Neural Network Training Strategy based on Generalized PolyDot codes (2018, background): “However, as the number of parallel processing units are scaling, the expected number of faults, errors or delays in computing are also scaling [3]–[8].”
Swayam: distributed autoscaling to meet SLAs of machine learning inference services with resource efficiency (2017, positive): “Google Search [15] uses a similar approach, but delays sending the redundant requests to limit useless work.”
An Open-Source Benchmark Suite for Microservices and Their Hardware-Software Implications for Cloud & Edge Systems (2019, background): “Many of these applications are interactive , latency-critical services that must meet strict performance (through-put and tail latency), and availability constraints, while also handling frequent software updates [21, 28–34, 36, 44, 51, 61, 62, 65].”