IDEAS home Printed from https://ideas.repec.org/a/spr/queues/v91y2019i3d10.1007_s11134-018-09597-5.html
   My bibliography  Save this article

Delay asymptotics and bounds for multitask parallel jobs

Author

Listed:
  • Weina Wang

    (University of Illinois at Urbana-Champaign
    Carnegie Mellon University)

  • Mor Harchol-Balter

    (Carnegie Mellon University)

  • Haotian Jiang

    (Tsinghua University)

  • Alan Scheller-Wolf

    (Carnegie Mellon University)

  • R. Srikant

    (University of Illinois at Urbana-Champaign)

Abstract

We study delay of jobs that consist of multiple parallel tasks, which is a critical performance metric in a wide range of applications such as data file retrieval in coded storage systems and parallel computing. In this problem, each job is completed only when all of its tasks are completed, so the delay of a job is the maximum of the delays of its tasks. Despite the wide attention this problem has received, tight analysis is still largely unknown since analyzing job delay requires characterizing the complicated correlation among task delays, which is hard to do. We first consider an asymptotic regime where the number of servers, n, goes to infinity, and the number of tasks in a job, $$k^{(n)}$$ k ( n ) , is allowed to increase with n. We establish the asymptotic independence of any $$k^{(n)}$$ k ( n ) queues under the condition $$k^{(n)}= o(n^{1/4})$$ k ( n ) = o ( n 1 / 4 ) . This greatly generalizes the asymptotic independence type of results in the literature, where asymptotic independence is shown only for a fixed constant number of queues. As a consequence of our independence result, the job delay converges to the maximum of independent task delays. We next consider the non-asymptotic regime. Here, we prove that independence yields a stochastic upper bound on job delay for any n and any $$k^{(n)}$$ k ( n ) with $$k^{(n)}\le n$$ k ( n ) ≤ n . The key component of our proof is a new technique we develop, called “Poisson oversampling.” Our approach converts the job delay problem into a corresponding balls-and-bins problem. However, in contrast with typical balls-and-bins problems where there is a negative correlation among bins, we prove that our variant exhibits positive correlation.

Suggested Citation

  • Weina Wang & Mor Harchol-Balter & Haotian Jiang & Alan Scheller-Wolf & R. Srikant, 2019. "Delay asymptotics and bounds for multitask parallel jobs," Queueing Systems: Theory and Applications, Springer, vol. 91(3), pages 207-239, April.
  • Handle: RePEc:spr:queues:v:91:y:2019:i:3:d:10.1007_s11134-018-09597-5
    DOI: 10.1007/s11134-018-09597-5
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s11134-018-09597-5
    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-018-09597-5?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. Graham, Carl & Méléard, Sylvie, 1993. "Propagation of chaos for a fully connected loss network with alternate routing," Stochastic Processes and their Applications, Elsevier, vol. 44(1), pages 159-180, January.
    2. Benjamin Melamed & Ward Whitt, 1990. "On Arrivals That See Time Averages," Operations Research, INFORMS, vol. 38(1), pages 156-172, February.
    3. Hongyuan Lu & Guodong Pang, 2017. "Heavy-traffic limits for an infinite-server fork–join queueing system with dependent and disruptive services," Queueing Systems: Theory and Applications, Springer, vol. 85(1), pages 67-115, February.
    4. Amr Rizk & Felix Poloczek & Florin Ciucu, 2016. "Stochastic bounds in Fork–Join queueing systems under full and partial mapping," Queueing Systems: Theory and Applications, Springer, vol. 83(3), pages 261-291, 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. Gorbunova, A.V. & Lebedev, A.V., 2023. "Nonlinear approximation of characteristics of a fork–join queueing system with Pareto service as a model of parallel structure of data processing," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 214(C), pages 409-428.
    2. Vladimir Mironovich Vishnevsky & Valentina Ivanovna Klimenok & Aleksandr Mikhailovich Sokolov & Andrey Alekseevich Larionov, 2024. "Investigation of the Fork–Join System with Markovian Arrival Process Arrivals and Phase-Type Service Time Distribution Using Machine Learning Methods," Mathematics, MDPI, vol. 12(5), pages 1-22, February.
    3. 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.

    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. Tetsuji Hirayama, 2003. "Mean sojourn times in multiclass feedback queues with gated disciplines," Naval Research Logistics (NRL), John Wiley & Sons, vol. 50(7), pages 719-741, October.
    2. Barbour, A.D. & Brightwell, Graham & Luczak, Malwina, 2022. "Long-term concentration of measure and cut-off," Stochastic Processes and their Applications, Elsevier, vol. 152(C), pages 378-423.
    3. A. Karthik & Arpan Mukhopadhyay & Ravi R. Mazumdar, 2017. "Choosing among heterogeneous server clouds," Queueing Systems: Theory and Applications, Springer, vol. 85(1), pages 1-29, February.
    4. (Yew Sing) Lee, Thomas, 1997. "A simple approach for analyzing feedback vacation queues with levy input process," European Journal of Operational Research, Elsevier, vol. 96(2), pages 299-316, January.
    5. Edieal J. Pinker & Robert A. Shumsky, 2000. "The Efficiency-Quality Trade-Off of Cross-Trained Workers," Manufacturing & Service Operations Management, INFORMS, vol. 2(1), pages 32-48, July.
    6. Gorbunova, A.V. & Lebedev, A.V., 2023. "Nonlinear approximation of characteristics of a fork–join queueing system with Pareto service as a model of parallel structure of data processing," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 214(C), pages 409-428.
    7. Erhun Özkan & Amy R. Ward, 2019. "On the Control of Fork-Join Networks," Mathematics of Operations Research, INFORMS, vol. 44(2), pages 532-564, May.
    8. Glynn, Peter & Sigman, Karl, 1998. "Independent sampling of a stochastic process," Stochastic Processes and their Applications, Elsevier, vol. 74(2), pages 151-164, June.
    9. David L. Jagerman & Benjamin Melamed, 2003. "Models and Approximations for Call Center Design," Methodology and Computing in Applied Probability, Springer, vol. 5(2), pages 159-181, June.
    10. Weiwei Chen & Benjamin Melamed & Oleg Sokolinskiy & Ben Sopranzetti, 2017. "Cash Conversion Systems in Corporate Subsidiaries," Manufacturing & Service Operations Management, INFORMS, vol. 19(4), pages 604-619, October.
    11. Hassin, Refael & Haviv, Moshe & Oz, Binyamin, 2023. "Strategic behavior in queues with arrival rate uncertainty," European Journal of Operational Research, Elsevier, vol. 309(1), pages 217-224.
    12. Tanabe, Yasuo, 2006. "The propagation of chaos for interacting individuals in a large population," Mathematical Social Sciences, Elsevier, vol. 51(2), pages 125-152, March.
    13. Schol, Dennis & Vlasiou, Maria & Zwart, Bert, 2023. "Tail asymptotics for the delay in a Brownian fork-join queue," Stochastic Processes and their Applications, Elsevier, vol. 164(C), pages 99-138.

    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:91:y:2019:i:3:d:10.1007_s11134-018-09597-5. 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.