IDEAS home Printed from https://ideas.repec.org/a/spr/queues/v83y2016i3d10.1007_s11134-016-9485-y.html
   My bibliography  Save this article

Queueing with redundant requests: exact analysis

Author

Listed:
  • Kristen Gardner

    (Carnegie Mellon University)

  • Samuel Zbarsky

    (Carnegie Mellon University)

  • Sherwin Doroudi

    (Carnegie Mellon University)

  • Mor Harchol-Balter

    (Carnegie Mellon University)

  • Esa Hyytiä

    (University of Iceland)

  • Alan Scheller-Wolf

    (Carnegie Mellon University)

Abstract

Recent computer systems research has proposed using redundant requests to reduce latency. The idea is to run a request on multiple servers and wait for the first completion (discarding all remaining copies of the request). However, there is no exact analysis of systems with redundancy. This paper presents the first exact analysis of systems with redundancy. We allow for any number of classes of redundant requests, any number of classes of non-redundant requests, any degree of redundancy, and any number of heterogeneous servers. In all cases we derive the limiting distribution of the state of the system. In small (two or three server) systems, we derive simple forms for the distribution of response time of both the redundant classes and non-redundant classes, and we quantify the “gain” to redundant classes and “pain” to non-redundant classes caused by redundancy. We find some surprising results. First, the response time of a fully redundant class follows a simple exponential distribution and that of the non-redundant class follows a generalized hyperexponential. Second, fully redundant classes are “immune” to any pain caused by other classes becoming redundant. We also compare redundancy with other approaches for reducing latency, such as optimal probabilistic splitting of a class among servers (Opt-Split) and join-the-shortest-queue (JSQ) routing of a class. We find that, in many cases, redundancy outperforms JSQ and Opt-Split with respect to overall response time, making it an attractive solution.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:queues:v:83:y:2016:i:3:d:10.1007_s11134-016-9485-y
    DOI: 10.1007/s11134-016-9485-y
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s11134-016-9485-y
    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-016-9485-y?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.

    Citations

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


    Cited by:

    1. Gideon Weiss, 2022. "Parallel multi-type many server conjecture," Queueing Systems: Theory and Applications, Springer, vol. 100(3), pages 269-271, April.
    2. Gideon Weiss, 2020. "Directed FCFS infinite bipartite matching," Queueing Systems: Theory and Applications, Springer, vol. 96(3), pages 387-418, December.
    3. 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.
    4. Kristen Gardner & Rhonda Righter, 2022. "The cost of collaboration," Queueing Systems: Theory and Applications, Springer, vol. 100(1), pages 7-40, February.
    5. 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.
    6. Céline Comte & Jan-Pieter Dorsman, 2021. "Pass-and-swap queues," Queueing Systems: Theory and Applications, Springer, vol. 98(3), pages 275-331, August.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. 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:83:y:2016:i:3:d:10.1007_s11134-016-9485-y. 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.

    We have no bibliographic references for this item. You can help adding them by using 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.