Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Stability and Optimization of Speculative Queueing Networks

Abstract : We provide a queueing-theoretic framework for job replication schemes based on the principle "replicate a job as soon as the system detects it as a straggler". This is called job speculation. Recent works have analyzed replication on arrival, which we refer to as replication. Replication is motivated by its implementation in Google's BigTable. However, systems such as Apache Spark and Hadoop MapReduce implement speculative job execution. The performance and optimization of speculative job execution is not well understood. To this end, we propose a queueing network model for load balancing where each server can speculate on the execution time of a job. Specifically, each job is initially assigned to a single server by a frontend dispatcher. Then, when its execution begins, the server sets a timeout. If the job completes before the timeout, it leaves the network, otherwise the job is terminated and relaunched or resumed at another server where it will complete. We provide a necessary and sufficient condition for the stability of speculative queueing networks with heterogeneous servers, general job sizes and scheduling disciplines. We find that speculation can increase the stability region of the network when compared with standard load balancing models and replication schemes. We provide general conditions under which timeouts increase the size of the stability region and derive a formula for the optimal speculation time, i.e., the timeout that minimizes the load induced through speculation. We compare speculation with redundant-d and redundant-to-idle-queued rules under an S&X model. For light loaded systems, redundancy schemes provide better response times. However, for moderate to heavy loadings, redundancy schemes can lose capacity and have markedly worse response times when compared with the proposed speculative scheme.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03349775
Contributor : Jonatha Anselmi Connect in order to contact the contributor
Submitted on : Monday, September 20, 2021 - 5:23:04 PM
Last modification on : Tuesday, October 19, 2021 - 11:19:15 AM

File

SQN.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03349775, version 1

Citation

Jonatha Anselmi, Neil Walton. Stability and Optimization of Speculative Queueing Networks. 2021. ⟨hal-03349775⟩

Share

Metrics

Record views

27

Files downloads

21