Redundancy scheduling with scaled Bernoulli service requirements

DOI10.1007/S11134-019-09621-2MaRDI QIDQ2294086zbMATH OpenOpenAlexWikidataFDO

Authors Youri Raaijmakers, Sem Borst, Onno Boxma

Publication date 10 February 2020

Published in Queueing Systems (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1811.06309

zbMATH Keywords

queueingstability conditionredundancydispatchingparallel-server systemsscaled Bernoulli service requirements

Mathematics Subject Classification ID

Queues and service in operations research (90B22) Deterministic scheduling theory in operations research (90B35) Queueing theory (aspects of probability theory) (60K25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Abstract: Redundancy scheduling has emerged as a powerful strategy for improving response times in parallel-server systems. The key feature in redundancy scheduling is replication of a job upon arrival by dispatching replicas to different servers. Redundant copies are abandoned as soon as the first of these replicas finishes service. By creating multiple service opportunities, redundancy scheduling increases the chance of a fast response from a server that is quick to provide service, and mitigates the risk of a long delay incurred when a single selected server turns out to be slow. The diversity enabled by redundant requests has been found to strongly improve the response time performance, especially in case of highly variable service requirements. Analytical results for redundancy scheduling are unfortunately scarce however, and even the stability condition has largely remained elusive so far, except for exponentially distributed service requirements. In order to gain further insight in the role of the service requirement distribution, we explore the behavior of redundancy scheduling for scaled Bernoulli service requirements. We establish a sufficient stability condition for generally distributed service requirements and we show that, for scaled Bernoulli service requirements, this condition is also asymptotically nearly necessary. This stability condition differs drastically from the exponential case, indicating that the stability condition depends on the service requirements in a sensitive and intricate manner.

Recommendations

• Redundancy-\(\mathbf{d}\): the power of \(\mathbf{d}\) choices for redundancy
• Queueing with redundant requests: exact analysis
• Parallel Server Systems with Cancel-on-Completion Redundancy
• Large-scale parallel server system with multi-component jobs
• Reducing Response Time in Fork-Join Systems under Heavy Traffic Via Imbalance Control

Cites work

• A Token-Based Central Queue with Order-Independent Service Rates
• Applied Probability and Queues
• On the Stability of Redundancy Models
• Probability and random processes.
• Queueing with redundant requests: exact analysis
• Redundancy-\(\mathbf{d}\): the power of \(\mathbf{d}\) choices for redundancy

Cited in

(14)

• Editorial introduction: second part of the special issue on product forms, stochastic matching, and redundancy
• The cost of collaboration
• A lower bound on the stability region of redundancy-\(d\) with FIFO service discipline
• Open problems in queueing theory inspired by datacenter computing
• Efficient scheduling in redundancy systems with general service times
• Editorial introduction: Special issue on product forms, stochastic matching, and redundancy
• On the Stability of Redundancy Models
• Heavy-traffic universality of redundancy systems with assignment constraints
• Product forms for FCFS queueing models with arbitrary server-job compatibilities: an overview
• Queueing with redundant requests: exact analysis
• Fork-join and redundancy systems with heavy-tailed job sizes
• On redundancy elimination tolerant scheduling rules
• A Survey of Stability Results for Redundancy Systems
• Redundancy-\(\mathbf{d}\): the power of \(\mathbf{d}\) choices for redundancy

This page was built for publication: Redundancy scheduling with scaled Bernoulli service requirements

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2294086)