Queues with Redundancy: Latency-Cost Analysis

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

47 citations recorded by the source corpus.

A major advantage of cloud computing and storage is the large-scale sharing of resources, which provides scalability and flexibility. But resource-sharing causes variability in the latency experienced by the user, due to several factors such as virtualization, server outages, network congestion etc . This problem is further aggravated when a job consists of several parallel tasks, because the task run on the slowest machine becomes the latency bottleneck. A promising method to reduce latency is to assign a task to multiple machines and wait for the earliest to finish. Similarly, in cloud storage systems requests to download the content can be assigned to multiple replicas, such that it is sufficient to download any one replica. Although studied actively in systems in the past few years, there is little work on rigorous analysis of how redundancy affects latency. The effect of redundancy in queueing systems was first analyzed only recently in [2, 3, 6], assuming exponential service time. General service time distribution, in particular the effect of its tail, is considered in [7, 8]. This work analyzes the trade-off between latency and the cost of computing resources in queues with redundancy, without assuming exponential service time. We study a generalized fork-join queueing model where finishing any k out of n tasks is sufficient to complete a job. The redundant tasks can be canceled when any k tasks finish, or earlier, when any k tasks start service. For the k = 1 case, we get an elegant latency and cost analysis by identifying equivalences between systems without and with early redundancy cancellation to M/G/1 and M/G/n queues respectively. For general k, we derive bounds on the latency and cost. Please see [4] for an extended version of this work.

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

In Management Information Systems

Citations in the corpus

Using Straggler Replication to Reduce Latency in Large-scale Parallel Computing (2015, methodology): “In [9] we analyze the e↵ect of queueing on the choice of the replication strategy.”
Communication-Computation Efficient Gradient Coding (2018, unknown): “, 2010; Ye & Barg, 2017), caching (Maddah-Ali & Niesen, 2015) and queuing (Joshi et al., 2015).”
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].”