When do redundant requests reduce latency ?

By Nihar B. Shah, Kangwook Lee, Kannan Ramchandran. 2013

191 citations recorded by the source corpus.

Several systems possess the flexibility to serve requests in more than one way. For instance, a distributed storage system storing multiple replicas of the data can serve a request from any of the multiple servers that store the requested data, or a computational task may be performed in a compute-cluster by any one of multiple processors. In such systems, the latency of serving the requests may potentially be reduced by sending redundant requests: a request may be sent to an excess number of servers, and it is deemed served when the requisite number of servers complete service. Such a mechanism trades off the possibility of faster execution of at least one copy of the request with the increase in the delay due to an increased load on the system. Due to this tradeoff, it is unclear when redundant requests may actually help. Several recent works empirically evaluate the latency performance of redundant requests in diverse settings. This work aims at a rigorous analytical study of the latency performance of redundant requests, with the primary goals of characterizing the situations when sending redundant requests will help (and when not), and designing optimal redundant-requesting policies. We first present a model that captures the key features of such systems. We show that when service times are i.i.d. memoryless or “heavy”, and when the additional copies of already-completed jobs can be removed with negligible costs, redundant requests reduce the average latency. On the other hand, when service times are “light” or when service times are memoryless and removal of jobs results in a non-negligible penalty, not having any redundancy in the request is optimal under high loads. Our results hold for arbitrary arrival processes.

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

Citations in the corpus

DRACO: Byzantine-resilient Distributed Training via Redundant Gradients (2018, methodology): “While early work on straggler mitigation used techniques such as job replication (Shah et al., 2016), more recent work has employed coding theory to speed up distributed machine learning systems (Lee et al.”
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.”
Gradient Coding Using the Stochastic Block Model (2018, background): “Current approaches include replicating jobs across nodes [3] and dropping stragglers in settings where the system can tolerate errors [4].”
Using Straggler Replication to Reduce Latency in Large-scale Parallel Computing (2015, methodology): “We note that using replication or redundancy to reduce latency has also attracted attention in other contexts such as cloud storage and networking applications [12, 13,17,19].”
Queues with Redundancy: Latency-Cost Analysis (2015, background): “General service time distribution, in particular the effect of its tail, is considered in [7, 8].”
Efficient Redundancy Techniques for Latency Reduction in Cloud Systems (2015, methodology): “New-better-than-used distributions are referred to as ‘light-everywhere’ in [Shah et al. 2013] and ‘new-longer-than-used’ in [Sun et al.”
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.”
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].”
Efficient task replication for fast response times in parallel computation (2014, unknown): “SIGMETRICS 14, June 16 20, 2014, Austin, Texas, USA.”
Communication-Computation Efficient Gradient Coding (2018, methodology): “The most popular ways to introduce redundancy in computation are based on either replication schemes or coding theoretic techniques (Ananthanarayanan et al., 2013; Wang et al., 2014; Shah et al., 2016; Lee et al., 2016).”