In modern computer systems, long-running jobs are divided into a large number of short tasks and executed in parallel. Experience in practical systems suggests that task service times are highly random and the job service latency is bottlenecked by the slowest straggling task. One common solution for straggler mitigation is to replicate a task on multiple servers and wait for one replica of the task to finish early. The delay performance of replications depends heavily on the scheduling decisions of when to replicate, which servers to replicate on, and which task to serve first. So far, little is understood on how to optimize these scheduling decisions for minimizing the job service latency . In this paper, we present a comprehensive theoretical analysis on delay-optimal scheduling in queueing systemswith replications. In particular, low-complexity replication policies are designed , and are rigorously proven to be delay-optimal or near delay-optimal among all non-preemptive and causal policies. These theoretical results are established for very general system settings and delay metrics which allow for arbitrary arrival process , arbitrary job sizes, arbitrary soft deadlines , and heterogeneous servers with data locality constraints. In order to prove these results , novel sufficient conditions are developed for sample-path delay optimality and near delay optimality, which can be applied to any queueing system and are not limited to the study of replications .
In modern computer systems, jobs are divided into short tasks and executed in parallel. Empirical observations in practical systems suggest that the task service times are highly random and the job service time is bottlenecked by the slowest straggling task. One common solution for straggler mitigation is to replicate a task on multiple servers and wait for one replica of the task to finish early. The delay performance of replications depends heavily on the scheduling decisions of when to replicate, which servers to replicate on, and which job to serve first. So far, little is understood on how to optimize these scheduling decisions for minimizing the delay to complete the jobs . In this paper, we present a comprehensive study on delay-optimal scheduling of replications in both centralized and distributed multi-server systems. Low-complexity scheduling policies are designed and are proven to be delay-optimal or near delay-optimal in stochastic ordering among all causal and non-preemptive policies. These theoretical results are established for general system settings and delay metrics that allow for arbitrary arrival processes , arbitrary job sizes, arbitrary due times , and heterogeneous servers with data locality constraints. Novel sample-path tools are developed to prove these results .
D
long-running
D
a large number of
R
Experience
Empirical observations
R
suggests that
suggest that the
R
latency
time
R
task
job
R
job service latency
delay to complete the jobs
R
theoretical analysis
study
R
in queueing systemswith replications. In particular, low-complexity replication
of replications in both centralized and distributed multi-server systems. Low-complexity scheduling
R
, and are rigorously
and are
R
among all
in stochastic ordering among all causal and
D
and causal
D
very
R
which
that
R
process
processes
R
soft deadlines
due times
R
In order
Novel sample-path tools are developed
D
, novel sufficient conditions are developed for sample-path delay optimality and near delay optimality, which can be applied to any queueing system and are not limited to the study of replications