Source-linked AI summary
When Do Redundant Requests Reduce Latency ?
Nihar B. Shah, Kangwook Lee, Kannan Ramchandran
TL;DR
Redundant requests trade faster completion of one copy against higher system load, leaving their latency benefit uncertain. This paper analytically models the tradeoff and derives optimal policies, showing that redundancy helps for memoryless or heavier service with instant removal, while no redundancy is optimal for lighter service or noninstant removal under high load.
Problem
It is unclear when redundant requests reduce latency because faster individual completion competes with the additional load they impose on the system.
Method
The paper develops an MDS-queue-based model and derives optimal redundant-requesting policies across several arrival, service, and removal-time distributions.
Results
Redundancy reduces average latency for memoryless or heavier service with instant removal, whereas no redundancy is optimal for lighter service or noninstant removal under high loads.
Takeaways & Limitations
The latency value of redundancy depends on service-time heaviness, removal cost, and load rather than following a universal rule.
Abstract
from arXiv · showhide
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 more servers than needed, 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 an analytical study of the latency performance of redundant requests, with the primary goals of characterizing under what scenarios sending redundant requests will help (and under what scenarios they will not help), as well as 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 "heavier", and when the additional copies of already-completed jobs can be removed instantly, redundant requests reduce the average latency. On the other hand, when service times are "lighter" or when service times are memoryless and removal of jobs is not instantaneous, then not having any redundancy in the requests is optimal under high loads. Our results hold for arbitrary arrival processes.
I. INTRODUCTION
Redundant requests may reduce latency by completing the first required copies, but they also increase system load, making their overall benefit uncertain. This paper develops an analytical model to characterize when redundancy helps and to derive optimal policies.
- I. INTRODUCTION: Redundant requests can lower individual-request latency because service completes after the fastest required copies finish.The same redundancy consumes additional resources and increases overall system load, which can worsen latency.
- I. INTRODUCTION: Prior work mainly evaluates redundant-request latency empirically, reporting reductions in some scenarios and increases in others.The paper identifies a lack of rigorous analysis determining when redundancy helps or does not help.
- I. INTRODUCTION: The paper uses an MDS-queue-based model to derive optimal redundant-requesting policies for several arrival, service, and removal-time distributions.The model is intended as a building block for more complex systems.
- I. INTRODUCTION: Table I summarizes when redundant requests reduce latency and which request policy is optimal under different distribution and load settings.High load means 100% server utilization; heavy-everywhere and light-everywhere are defined later in the paper.
- I. INTRODUCTION: The analysis allows arbitrary arrival sequences and does not require asymptotic steady-state assumptions.This broadens the arrival-process and operating-regime scope of the results.
II. RELATED LITERATURE
Previous studies largely evaluate redundant requests empirically and find mixed latency effects. The paper positions its contribution as a theoretical characterization of when redundancy helps or fails to help.
- II. RELATED LITERATURE: Empirical studies examine redundant requests across several applications and report latency reductions in many cases.The related work includes application settings such as computation performed on processors.
- II. RELATED LITERATURE: The paper identifies little theoretical characterization of the settings in which redundant requests help reduce latency.This theoretical gap is stated as the motivation for the paper’s analysis.
- II. RELATED LITERATURE: An existing theoretical study bounds steady-state latency when requests are redundantly sent to all servers but does not compare alternative redundancy schemes.It also does not compare against the no-redundancy scheme.
III. SYSTEM MODEL: CENTRALIZED BUFFER
The centralized model has n servers and a common infinite-capacity buffer, with each request assigned a configurable number r of redundant jobs. A request completes after k jobs finish, while unfinished copies may incur removal costs.
- III. SYSTEM MODEL: CENTRALIZED BUFFER: The system contains n servers, and any request can be served by any k distinct servers.The parameters n and k describe the system, while r describes the redundant-requesting policy.
- III. SYSTEM MODEL: CENTRALIZED BUFFER: Each request is represented as a batch of r jobs, and the batch is served when any k of those jobs complete.The request-degree satisfies k ≤ r ≤ n.
- III. SYSTEM MODEL: CENTRALIZED BUFFER: After k jobs complete, the remaining r − k jobs are removed from the system.If removal is not instantaneous, the server may remain idle for a random removal cost before serving another job.
- III. SYSTEM MODEL: CENTRALIZED BUFFER: The scheduling policy is first-come-first-served among waiting jobs that an idle server can serve.The model assumes independent service times and stability when r = k, the no-redundancy case.
- III. SYSTEM MODEL: CENTRALIZED BUFFER: Requests enter a common infinite-capacity buffer, and servers may be chosen to serve jobs at any point in time.This centralized choice differs from the later distributed-buffer setting, where assignment occurs on arrival.
- III. SYSTEM MODEL: CENTRALIZED BUFFER: r = k represents no redundancy, whereas r = n represents maximum redundancy, sending each batch to all servers.The illustrative example uses n = 4, k = 2, and r = 3.
IV. ANALYTICAL RESULTS FOR THE CENTRALIZED BUFFER SETTING
The centralized-buffer analysis identifies when redundancy lowers average latency and when no redundancy is optimal, based on service-time tails and removal costs. Under high load, heavier service favors maximal redundancy, whereas lighter service or costly removal favors no redundancy.
- Memoryless service: For memoryless service with instantaneous removal, average latency decreases as request-degree increases, for both k = 1 and general k.Theorems 1 and 2 establish that maximal redundancy, r = n, minimizes average latency.
- Heavy-everywhere service: Heavy-everywhere service with instantaneous removal is minimized by sending each batch to all n servers at 100% utilization.Theorem 3 gives r = n as optimal for k = 1 under high load; simulations suggest the same policy may minimize latency at all loads and for k > 1.
- Light-everywhere service: Light-everywhere service is minimized by no redundancy at 100% utilization, regardless of removal cost.Light-everywhere distributions include shifted exponentials and uniform distributions; the condition means residual waiting decreases after elapsed service time.
- Light-everywhere service: For light-everywhere service, simulations show redundancy helps at low arrival rates but begins hurting beyond a load threshold.At high loads, r = 1 minimizes average latency, consistent with the theorem; similar behavior appears for k > 1.
- Removal costs: With memoryless service and non-zero removal delay, no redundancy minimizes average latency at 100% utilization.Simulations likewise show higher latency for redundant requests at high loads.
V. SYSTEM MODEL: DISTRIBUTED BUFFERS
The distributed-buffer model gives each server its own buffer, requiring each arriving batch to be assigned immediately to a selected subset of servers. The paper permits arbitrary selection protocols, with least-loaded buffers offered as a concrete example.
- Distributed-buffer operation: Each server has an individual buffer, and a batch’s jobs must be sent to selected server buffers when the batch arrives.The distributed setting differs from a centralized buffer because jobs are assigned immediately to some of the n buffers.
- Distributed-buffer operation: The protocol may choose any r servers for each batch; selecting the r least-loaded buffers is one concrete policy.
- Example: With n = 4, k = 2, and r = 3, a batch is sent to three buffers, and completion of two jobs removes the remaining copy.In the example, servers 2 and 3 then begin serving jobs from the next batch, while server 1 remains idle because its buffer is empty.
VI. ANALYTICAL RESULTS FOR THE DISTRIBUTED BUFFERS SETTING
The distributed-buffer results identify when redundancy is optimal or harmful under high utilization. Redundancy is favored for memoryless or heavy service with instantaneous removal, whereas no redundancy is optimal for light service or nonzero removal cost.
- Memoryless service: For i.i.d. memoryless service with instantaneous job removal, sending every batch to all n servers minimizes average latency.This result applies for general k, when any k servers can serve a request.
- Heavy-everywhere service: At 100% server utilization, heavy-everywhere service with k = 1 is optimized by sending every batch to all n servers.The theorem assumes instantaneous removal of completed-job copies.
- Light-everywhere service: At 100% server utilization, light-everywhere service with k = 1 is optimized by having no redundancy, r = k (= 1).This conclusion holds for any removal cost.
- Removal cost: At 100% server utilization, i.i.d. memoryless service with nonzero removal delay is optimized by having no redundancy, r = k (= 1).
- Restricted server eligibility: In the illustrated n = 20, m = 10, k = 5 exponential-service system without removal cost, average latency decreases as request redundancy increases.For each batch, the eligible subset of m = 10 servers is chosen uniformly from the n = 20 servers.
VII. CONCLUSIONS AND OPEN PROBLEMS
The paper analytically characterizes settings in which redundant requests help or hurt and derives optimal requesting policies for those settings. It closes by identifying broader service, workload, heterogeneity, metric, adaptivity, and eligibility questions as open problems.
- Conclusions: The paper proposes a model capturing key system features, analytically characterizes several settings, and derives an optimal redundant-requesting policy for each.
- Open problems: Characterization remains open for many more general settings beyond those analyzed in the paper.
- Open problems: Open questions include service-time distributions and removal costs not considered, heterogeneous requests or servers, non-i.i.d. batch jobs, and latency-tail metrics.
- Open problems: The paper also leaves open adaptive choices of request degree and which results extend when each request can use only m < n servers.
APPENDIX A HEAVY-EVERYWHERE AND LIGHT-EVERYWHERE DISTRIBUTIONS
This appendix characterizes heavy-everywhere and light-everywhere service-time distributions through minimum expectations, mixtures, sums, and examples.
- For heavy-everywhere distributions, the expected minimum of n independent samples is no larger than 1.
- For light-everywhere distributions, the expected minimum of n independent samples is no smaller than n times the distribution's expected value.
- A finite mixture of independent heavy-everywhere distributions remains heavy-everywhere when their survival-ordering condition holds across all thresholds.
- Examples of heavy-everywhere distributions include finite mixtures of independently drawn exponential distributions and Weibull distributions with scale parameter smaller than 1.
- The sum of finitely many independent light-everywhere random variables is light-everywhere.
- Examples of light-everywhere distributions include constants, positively shifted exponentials, uniform distributions, and certain two-point distributions.
APPENDIX B PROOFS
The appendix develops a coupling-based proof technique that compares redundant-requesting policies through hypothetical systems and shared event sequences. The resulting comparisons establish latency and occupancy orderings, including strict improvements under specific service-time conditions, while applying to arbitrary arrivals and non-steady-state intervals.
- General proof technique: The proof constructs hypothetical systems T1 and T2 whose performance bounds or matches systems S1 and S2, then couples them for comparison.The construction uses corresponding service events and the same arrival sequence in both systems.
- Scope: The proof technique handles arbitrary arrival sequences and applies beyond asymptotic steady state to any time interval.This broadens the analytical results beyond assumptions tied to a particular arrival process or steady-state regime.
- General proof technique: Under the coupling, T2 has no more remaining batches than T1 at event times, implying no greater average latency through system occupancy.The argument uses stochastic dominance of occupancy and the proportionality between average latency and average occupancy.
- Memoryless service: With memoryless service and no removal cost, increasing request degree strictly lowers average latency, and request degree n is optimal among redundant-requesting policies.The proof compares any fixed degree r < n with serving each batch on all n servers, and extends the result to adaptive policies.
- Heavy-everywhere distributions: For heavy-everywhere service distributions satisfying a strict inequality with positive probability, full request degree yields strictly lower latency than any fixed degree r < n.The construction can introduce a non-trivial gap between the comparison systems, which transfers to the original systems.
- Light-everywhere distributions: For light-everywhere distributions satisfying the corresponding strict inequality with positive probability, the same comparison also yields strictly lower latency for the higher request degree.Here the construction makes T1 better than S1 by a non-trivial amount before transferring the ordering to S1 and S2.