Efficient Redundancy Techniques for Latency Reduction in Cloud Systems

By Gauri Joshi, Emina Soljanin, Gregory W. Wornell. 2015

138 citations recorded by the source corpus.

In cloud computing systems, assigning a task to multiple servers and waiting for the earliest copy to finish is an effective method to combat the variability in response time of individual servers and reduce latency. But adding redundancy may result in higher cost of computing resources, as well as an increase in queueing delay due to higher traffic load. This work helps in understanding when and how redundancy gives a cost-efficient reduction in latency. For a general task service time distribution, we compare different redundancy strategies in terms of the number of redundant tasks and the time when they are issued and canceled. We get the insight that the log-concavity of the task service time creates a dichotomy of when adding redundancy helps. If the service time distribution is log-convex (i.e., log of the tail probability is convex), then adding maximum redundancy reduces both latency and cost. And if it is log-concave (i.e., log of the tail probability is concave), then less redundancy, and early cancellation of redundant tasks is more effective. Using these insights, we design a general redundancy strategy that achieves a good latency-cost trade-off for an arbitrary service time distribution. This work also generalizes and extends some results in the analysis of fork-join queues.

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

Speeding Up Distributed Machine Learning Using Codes (2015, background): “[36] study the cost associated with scheduling of redundant requests, and propose a general scheduling policy that achieves a delicate balance between the latency performance and the cost.”
Rateless codes for near-perfect load balancing in distributed matrix-vector multiplication (2018, methodology): “Queueing models to analyze the latency of coded content download jobs were proposed and analyzed in [23]–[27].”
Queues with Redundancy: Latency-Cost Analysis (2015, background): “All proofs are omitted here and can be found in the extended version [4].”
Distributed and Private Coded Matrix Computation with Flexible Communication Load (2019, unknown): “, [2].”
Analyzing the download time of availability codes (2015, methodology): “This work is a continuation of our effort to understand the impact of erasure coding on download time [3, 26, 28, 29].”