{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:29:49Z","timestamp":1750220989717,"version":"3.41.0"},"reference-count":65,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,3,3]],"date-time":"2019-03-03T00:00:00Z","timestamp":1551571200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"German Research Foundation (DFG) as part of projects C3 and B4 within the Collaborative Research Center","award":["1053?MAKI"],"award-info":[{"award-number":["1053?MAKI"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Model. Perform. Eval. Comput. Syst."],"published-print":{"date-parts":[[2019,3,31]]},"abstract":"<jats:p>Parallel server frameworks are widely deployed in modern large-data processing applications. Intuitively, splitting and parallel processing of the workload provides accelerated application response times and scaling flexibility. Examples of such frameworks include MapReduce, Hadoop, and Spark. For many applications, the dynamics of such systems are naturally captured by a Fork-Join (FJ) queuing model, where incoming jobs are split into tasks each of which is mapped to exactly one server. When all the tasks that belong to one job are executed, the job is reassembled and leaves the system. We consider this behavior at the output as a synchronization constraint.<\/jats:p><jats:p>In this article, we study the performance of such parallel systems for different server properties, e.g., work-conservingness, phase-type behavior, and as suggested by recent evidence, for bursty input job arrivals. We establish a Large Deviations Principle for the steady-state job waiting times in an FJ system based on Markov-additive processes. Building on that, we present a performance analysis framework for FJ systems and provide computable bounds on the tail probabilities of the steady-state waiting times. We validate our bounds using estimates obtained through simulations. In addition, we define and analyze provisioning, a flexible division of jobs into tasks, in FJ systems. Finally, we use this framework together with real-world traces to show the benefits of an adaptive provisioning system that adjusts the service within an FJ system based on the arrival intensity.<\/jats:p>","DOI":"10.1145\/3300142","type":"journal-article","created":{"date-parts":[[2019,3,4]],"date-time":"2019-03-04T13:31:47Z","timestamp":1551706307000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Provisioning and Performance Evaluation of Parallel Systems with Output Synchronization"],"prefix":"10.1145","volume":"4","author":[{"given":"Wasiur R.","family":"KhudaBukhsh","sequence":"first","affiliation":[{"name":"Technische Universit\u00e4t Darmstadt, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sounak","family":"Kar","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Darmstadt, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amr","family":"Rizk","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Darmstadt, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Heinz","family":"Koeppl","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Darmstadt, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,3,3]]},"reference":[{"volume-title":"Retrieved","year":"2017","author":"Inc.","key":"e_1_2_1_1_1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"R. Atar A. Mandelbaum and A. Zviran. 2012. Control of fork-join networks in heavy traffic. In Allerton. 823--830. R. Atar A. Mandelbaum and A. Zviran. 2012. Control of fork-join networks in heavy traffic. In Allerton. 823--830.","DOI":"10.1109\/Allerton.2012.6483303"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Kendall E. Atkinson. 2008. The Numerical Solution of Integral Equations of the Second Kind. Cambridge University Press. Kendall E. Atkinson. 2008. The Numerical Solution of Integral Equations of the Second Kind. Cambridge University Press.","DOI":"10.1007\/978-1-4419-0458-4_12"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807128.1807150"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.21076"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Francois Baccelli Armand M. Makowski and Adam Shwartz. 1989. The fork-join queue and related systems with synchronization constraints: Stochastic ordering and computable bounds. Advances in Applied Probability (1989) 629--660. Francois Baccelli Armand M. Makowski and Adam Shwartz. 1989. The fork-join queue and related systems with synchronization constraints: Stochastic ordering and computable bounds. Advances in Applied Probability (1989) 629--660.","DOI":"10.2307\/1427640"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/65950.65957"},{"key":"e_1_2_1_8_1","unstructured":"Christopher T. H. Baker. 1977. The Numerical Treatment of Integral Equations. Oxford University Press. Christopher T. H. Baker. 1977. The Numerical Treatment of Integral Equations. Oxford University Press."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.730531"},{"key":"e_1_2_1_10_1","first-page":"79","article-title":"Order statistics for nonidentically distributed variables and permanents","volume":"51","author":"Bapat R. B.","year":"1989","journal-title":"Sankhya Ser A"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10260-003-0068-9"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"D. Barber. 2012. Bayesian Reasoning and Machine Learning. Cambridge University Press. D. Barber. 2012. Bayesian Reasoning and Machine Learning. Cambridge University Press.","DOI":"10.1017\/CBO9780511804779"},{"key":"e_1_2_1_13_1","unstructured":"Onno Johan Boxma Ger Koole and Zhen Liu. 1994. Queueing-theoretic Solution Methods for Models of Parallel and Distributed Systems. Centrum voor Wiskunde en Informatica Department of Operations Research Statistics and System Theory. Onno Johan Boxma Ger Koole and Zhen Liu. 1994. Queueing-theoretic Solution Methods for Models of Parallel and Distributed Systems. Centrum voor Wiskunde en Informatica Department of Operations Research Statistics and System Theory."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.2307\/3215328"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11134-016-9512-z"},{"key":"e_1_2_1_16_1","unstructured":"Joseph Hellerstein Charles Reiss and John Wilkes. 2013. Google Cluster-usage Traces. Retrieved from https:\/\/github.com\/google\/cluster-data. Joseph Hellerstein Charles Reiss and John Wilkes. 2013. Google Cluster-usage Traces. Retrieved from https:\/\/github.com\/google\/cluster-data."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.946659"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2010.168"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/2367502.2367519"},{"volume":"1","volume-title":"Proceedings of the 2016 28th International Teletraffic Congress (ITC 28)","author":"Ciucu F.","key":"e_1_2_1_20_1"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Amir Dembo and Ofer Zeitouni. 2010. Large Deviations Techniques and Applications. Springer-Verlag Berlin. Amir Dembo and Ofer Zeitouni. 2010. Large Deviations Techniques and Applications. Springer-Verlag Berlin.","DOI":"10.1007\/978-3-642-03311-7"},{"key":"e_1_2_1_23_1","first-page":"413","article-title":"Exponential bounds for queues with markovian arrivals. Que","volume":"17","author":"Duffield N. G.","year":"1994","journal-title":"Syst."},{"volume-title":"Proceedings of the IEEE International Conference on Computer Communications (INFOCOM\u201916)","author":"Fidler M.","key":"e_1_2_1_24_1"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/IDAACS.2015.7341448"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0144074"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3135974.3135979"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Ayalvadi J. Ganesh Neil O\u2019Connell and Damon J. Wischik. 2004. Big Queues. Springer-Verlag Berlin. Ayalvadi J. Ganesh Neil O\u2019Connell and Damon J. Wischik. 2004. Big Queues. Springer-Verlag Berlin.","DOI":"10.1007\/978-3-540-39889-9"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1999.1577"},{"key":"e_1_2_1_30_1","unstructured":"Theodore Edward Harris. 1963. The Theory of Branching Processes. Springer-Verlag Berlin. Theodore Edward Harris. 1963. The Theory of Branching Processes. Springer-Verlag Berlin."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00375-4"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11192-016-1945-y"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.1986.1146393"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2013.03.007"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-8858(85)90017-X"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2014.140518"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/ALLERTON.2015.7446992"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055281"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1644893.1644918"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2825236.2825256"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2018.8486310"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2017.8057013"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.16501"},{"key":"e_1_2_1_44_1","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1111\/j.2517-6161.1970.tb00819.x","article-title":"Inequalities in the theory of queues","volume":"32","author":"Kingman J. F. C.","year":"1970","journal-title":"J. Roy. Stat. Soc. Ser. B"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/324138.324264"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2094114.2094118"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2017.08.008"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.2213"},{"key":"e_1_2_1_49_1","doi-asserted-by":"crossref","unstructured":"P. Ney and E. Nummelin. 1987. Markov additive processes II. large deviations. Ann. Probab. 15 2 (04 1987) 593--609. P. Ney and E. Nummelin. 1987. Markov additive processes II. large deviations. Ann. Probab. 15 2 (04 1987) 593--609.","DOI":"10.1214\/aop\/1176992160"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jss.2015.08.036"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jnca.2014.07.022"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2014.07.004"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2015.06.007"},{"key":"e_1_2_1_54_1","doi-asserted-by":"crossref","unstructured":"Carl Edward Rasmussen and Christopher K. I. Williams. 2006. Gaussian Processes for Machine Learning. The MIT Press. Carl Edward Rasmussen and Christopher K. I. Williams. 2006. Gaussian Processes for Machine Learning. The MIT Press.","DOI":"10.7551\/mitpress\/3206.001.0001"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2796314.2745859"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2483977.2484009"},{"volume-title":"Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC\u201916)","author":"Shastri S.","key":"e_1_2_1_57_1"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/2628913"},{"key":"e_1_2_1_59_1","doi-asserted-by":"crossref","unstructured":"S. R. S. Varadhan. 2016. Large Deviations. American Mathematical Soceity. S. R. S. Varadhan. 2016. Large Deviations. American Mathematical Soceity.","DOI":"10.1090\/cln\/027"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/1269899.1254898"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1016616406118"},{"volume-title":"Proceedings of the USENIX Workshop on Hot Topics in Cloud Computing (USENIX HotCloud\u201910)","year":"2010","author":"Zaharia Matei","key":"e_1_2_1_62_1"},{"key":"e_1_2_1_63_1","volume-title":"Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (USENIX OSDI\u201908)","volume":"8","author":"Zaharia Matei","year":"2008"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/2896377.2901470"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/1811039.1811073"}],"container-title":["ACM Transactions on Modeling and Performance Evaluation of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3300142","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3300142","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:25:22Z","timestamp":1750206322000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3300142"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,3]]},"references-count":65,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,3,31]]}},"alternative-id":["10.1145\/3300142"],"URL":"https:\/\/doi.org\/10.1145\/3300142","relation":{},"ISSN":["2376-3639","2376-3647"],"issn-type":[{"type":"print","value":"2376-3639"},{"type":"electronic","value":"2376-3647"}],"subject":[],"published":{"date-parts":[[2019,3,3]]},"assertion":[{"value":"2018-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-03-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}