Delay asymptotics and bounds for multitask parallel jobs

Weina Wang (), Mor Harchol-Balter (), Haotian Jiang (), Alan Scheller-Wolf () and R. Srikant ()
Additional contact information
Weina Wang: University of Illinois at Urbana-Champaign
Mor Harchol-Balter: Carnegie Mellon University
Haotian Jiang: Tsinghua University
Alan Scheller-Wolf: Carnegie Mellon University
R. Srikant: University of Illinois at Urbana-Champaign

Queueing Systems: Theory and Applications, 2019, vol. 91, issue 3, No 2, 207-239

Abstract: 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.

Keywords: Large systems; Asymptotic independence; Association of random variables; Parallel jobs; 68M20; 60K25 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s11134-018-09597-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:queues:v:91:y:2019:i:3:d:10.1007_s11134-018-09597-5

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/11134/

DOI: 10.1007/s11134-018-09597-5

Access Statistics for this article

Queueing Systems: Theory and Applications is currently edited by Sergey Foss

More articles in Queueing Systems: Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().