IDEAS home Printed from https://ideas.repec.org/a/spr/queues/v93y2019i1d10.1007_s11134-019-09621-2.html
   My bibliography  Save this article

Redundancy scheduling with scaled Bernoulli service requirements

Author

Listed:
  • Youri Raaijmakers

    (Eindhoven University of Technology)

  • Sem Borst

    (Eindhoven University of Technology
    Nokia Bell Labs)

  • Onno Boxma

    (Eindhoven University of Technology)

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 the 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.

Suggested Citation

  • Youri Raaijmakers & Sem Borst & Onno Boxma, 2019. "Redundancy scheduling with scaled Bernoulli service requirements," Queueing Systems: Theory and Applications, Springer, vol. 93(1), pages 67-82, October.
    • Handle: RePEc:spr:queues:v:93:y:2019:i:1:d:10.1007_s11134-019-09621-2
    DOI: 10.1007/s11134-019-09621-2
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s11134-019-09621-2
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s11134-019-09621-2?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Kristen Gardner & Samuel Zbarsky & Sherwin Doroudi & Mor Harchol-Balter & Esa Hyytiä & Alan Scheller-Wolf, 2016. "Queueing with redundant requests: exact analysis," Queueing Systems: Theory and Applications, Springer, vol. 83(3), pages 227-259, August.
    2. Kristen Gardner & Mor Harchol-Balter & Alan Scheller-Wolf & Mark Velednitsky & Samuel Zbarsky, 2017. "Redundancy-d: The Power of d Choices for Redundancy," Operations Research, INFORMS, vol. 65(4), pages 1078-1094, August.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Kristen Gardner, 2022. "Correlation in redundancy systems," Queueing Systems: Theory and Applications, Springer, vol. 100(3), pages 197-199, April.
    2. Kristen Gardner & Rhonda Righter, 2022. "The cost of collaboration," Queueing Systems: Theory and Applications, Springer, vol. 100(1), pages 7-40, February.
    3. Youri Raaijmakers & Sem Borst & Onno Boxma, 2023. "Fork–join and redundancy systems with heavy-tailed job sizes," Queueing Systems: Theory and Applications, Springer, vol. 103(1), pages 131-159, February.
    4. Mor Harchol-Balter, 2021. "Open problems in queueing theory inspired by datacenter computing," Queueing Systems: Theory and Applications, Springer, vol. 97(1), pages 3-37, February.
    5. Jonatha Anselmi, 2022. "Replication vs speculation for load balancing," Queueing Systems: Theory and Applications, Springer, vol. 100(3), pages 389-391, April.
    6. Kristen Gardner & Rhonda Righter, 2020. "Product forms for FCFS queueing models with arbitrary server-job compatibilities: an overview," Queueing Systems: Theory and Applications, Springer, vol. 96(1), pages 3-51, October.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Mor Harchol-Balter, 2021. "Open problems in queueing theory inspired by datacenter computing," Queueing Systems: Theory and Applications, Springer, vol. 97(1), pages 3-37, February.
    2. Kristen Gardner & Rhonda Righter, 2022. "The cost of collaboration," Queueing Systems: Theory and Applications, Springer, vol. 100(1), pages 7-40, February.
    3. Kristen Gardner & Rhonda Righter, 2020. "Product forms for FCFS queueing models with arbitrary server-job compatibilities: an overview," Queueing Systems: Theory and Applications, Springer, vol. 96(1), pages 3-51, October.
    4. Zhao, Chen & Wang, Zhongbin, 2023. "The impact of line-sitting on a two-server queueing system," European Journal of Operational Research, Elsevier, vol. 308(2), pages 782-800.
    5. Francisco Castro & Hamid Nazerzadeh & Chiwei Yan, 2020. "Matching queues with reneging: a product form solution," Queueing Systems: Theory and Applications, Springer, vol. 96(3), pages 359-385, December.
    6. Kristen Gardner, 2022. "Correlation in redundancy systems," Queueing Systems: Theory and Applications, Springer, vol. 100(3), pages 197-199, April.
    7. Seva Shneer & Alexander L. Stolyar, 2021. "Large-scale parallel server system with multi-component jobs," Queueing Systems: Theory and Applications, Springer, vol. 98(1), pages 21-48, June.
    8. Jonatha Anselmi & Francois Dufour, 2020. "Power-of- d -Choices with Memory: Fluid Limit and Optimality," Mathematics of Operations Research, INFORMS, vol. 45(3), pages 862-888, August.
    9. Céline Comte & Jan-Pieter Dorsman, 2021. "Pass-and-swap queues," Queueing Systems: Theory and Applications, Springer, vol. 98(3), pages 275-331, August.
    10. Gideon Weiss, 2022. "Parallel multi-type many server conjecture," Queueing Systems: Theory and Applications, Springer, vol. 100(3), pages 269-271, April.
    11. Gideon Weiss, 2020. "Directed FCFS infinite bipartite matching," Queueing Systems: Theory and Applications, Springer, vol. 96(3), pages 387-418, December.
    12. Leela Nageswaran, 2023. "Implications of vaccine shopping during pandemic," Production and Operations Management, Production and Operations Management Society, vol. 32(4), pages 1133-1149, April.
    13. Jinsheng Chen & Jing Dong & Pengyi Shi, 2020. "A survey on skill-based routing with applications to service operations management," Queueing Systems: Theory and Applications, Springer, vol. 96(1), pages 53-82, October.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:queues:v:93:y:2019:i:1:d:10.1007_s11134-019-09621-2. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.