Redundancy scheduling with scaled Bernoulli service requirements

DOI10.1007/S11134-019-09621-2zbMATH Open1494.68032arXiv1811.06309OpenAlexW2963551975WikidataQ127635850 ScholiaQ127635850MaRDI QIDQ2294086FDOQ2294086

Authors: Youri Raaijmakers, Sem Borst, Onno Boxma 

Publication date: 10 February 2020

Published in: Queueing Systems (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

Cited In (14)

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

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)