{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,22]],"date-time":"2026-06-22T21:40:45Z","timestamp":1782164445827,"version":"3.54.5"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"1","funder":[{"name":"TECoSA Vinnova Center","award":["2024-03717"],"award-info":[{"award-number":["2024-03717"]}]},{"name":"ERC NEMO","award":["788851"],"award-info":[{"award-number":["788851"]}]},{"name":"TUCAN6-CM","award":["TEC-2024&#x5c;&#x2f;COM-460"],"award-info":[{"award-number":["TEC-2024&#x5c;&#x2f;COM-460"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2026,3,26]]},"abstract":"<jats:p>\n                    Cloud computing data centers handle highly variable workloads: job resource requirements can range from just one or few cores to thousands, and job service times can range from milliseconds to hours or days. This variability significantly limits the maximum achievable utilization of infrastructures. Queuing theory has addressed the study of these systems with the definition of the Multiserver-Job Queuing Model (MJQM), where\n                    <jats:italic toggle=\"yes\">s<\/jats:italic>\n                    identical servers are present and job\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    requires \u03b1\n                    <jats:sub>\n                      <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    <\/jats:sub>\n                    of the\n                    <jats:italic toggle=\"yes\">s<\/jats:italic>\n                    servers for a random amount of time \u03c3\n                    <jats:sub>\n                      <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    <\/jats:sub>\n                    . The \u03b1\n                    <jats:sub>\n                      <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    <\/jats:sub>\n                    servers are occupied and released simultaneously. Unfortunately, despite its simple formulation, the MJQM remains elusive. For example, the MJQM stability condition has been derived only in particular cases. As a consequence, even applying Discrete-Event Simulation (DES) under high load becomes challenging, because stability cannot be determined a priori. In this paper, we analyze the MJQM with general independent arrival processes and service times under FCFS scheduling, using stochastic recurrence equations (SREs) and ergodic theory. Starting from the definition of the MJQM SRE, we prove the monotonicity and separability properties that allow us to apply an extension of Loynes' theorem, known as the monotone-separable framework, and formally define the MJQM stability condition. From these results, we introduce and implement two algorithms: the first one is used to draw sub-perfect samples (SPS) of the system's workload and the second one estimates the system's stability condition given the statistics of the jobs' input stream. The nature of the SPS algorithm allows for a massive GPU parallelization, thus greatly improving the efficiency in the estimation of performance metrics. The algorithm for the estimation of the stability condition solves an important problem for the analysis of MJQMs. We also define new metrics that capture the synchronization loss in MJQM systems and we show how these metrics can be efficiently evaluated using the SRE approach. Finally, we show that the approach proposed in this paper can be extended to more complicated systems, including MJQMs where resources have types.\n                  <\/jats:p>","DOI":"10.1145\/3788105","type":"journal-article","created":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T18:49:47Z","timestamp":1774550987000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["The Multiserver-Job Stochastic Recurrence Equation for Cloud Computing Performance Evaluation"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9326-8422","authenticated-orcid":false,"given":"Fran\u00e7ois","family":"Baccelli","sequence":"first","affiliation":[{"name":"INRIA, Paris, France and T\u00e9l\u00e9com Paris, Paris, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7361-819X","authenticated-orcid":false,"given":"Diletta","family":"Olliaro","sequence":"additional","affiliation":[{"name":"Universit\u00e0 Ca' Foscari Venezia, Venice, Italy and KTH Royal Institute of Technology, Stockholm, Sweden"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9560-7053","authenticated-orcid":false,"given":"Marco","family":"Ajmone Marsan","sequence":"additional","affiliation":[{"name":"IMDEA Networks Institute, Madrid, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5958-1204","authenticated-orcid":false,"given":"Andrea","family":"Marin","sequence":"additional","affiliation":[{"name":"Universit\u00e0 Ca' Foscari Venezia, Venice, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,3,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11009-019-09721-9"},{"key":"e_1_2_1_2_1","first-page":"1","article-title":"The Non-Saturated Multiserver Job Queuing Model with Two Job Classes: a Matrix Geometric Analysis. In 2024 MASCOTS. IEEE","author":"Anggraito A.","year":"2024","unstructured":"A. Anggraito, D. Olliaro, A. Marin, and M. Ajmone Marsan. 2024. The Non-Saturated Multiserver Job Queuing Model with Two Job Classes: a Matrix Geometric Analysis. In 2024 MASCOTS. IEEE, New York, USA, 1-8.","journal-title":"New York, USA"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2025.102486"},{"key":"e_1_2_1_4_1","unstructured":"F. Baccelli and P. Br\u00e9maud. 1994. Elements of Queueing Theory. Springer Heidelberg Germany."},{"key":"e_1_2_1_5_1","volume-title":"Parallel Simulation of Stochastic Petri Nets Using Recursive Equations. ACM Transactions on Modeling and Computer Simulation (TOMACS)","volume":"41","author":"Baccelli F.","unstructured":"F. Baccelli and M. Canales. 1993. Parallel Simulation of Stochastic Petri Nets Using Recursive Equations. ACM Transactions on Modeling and Computer Simulation (TOMACS), Vol. 3(1) (1993), 20-41."},{"key":"e_1_2_1_6_1","unstructured":"F. Baccelli G. Cohen G.J. Olsder and J-P. Quadrat. 1992. Synchronization and Linearity. Wiley Hoboken NJ USA."},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"F. Baccelli C. A. Courcoubetis and M. I. Reiman. 1987. Construction of the stationary regime of queues with locking. Stochastic Processes and their Applications Vol. 26 (1987) 257-265.","DOI":"10.1016\/0304-4149(87)90179-7"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.2307\/3215303"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","first-page":"621","DOI":"10.1214\/105051604000000044","article-title":"Moments and Tails in Monotone-Separable Stochastic Networks","volume":"14","author":"Baccelli F.","year":"2004","unstructured":"F. Baccelli and S. Foss. 2004. Moments and Tails in Monotone-Separable Stochastic Networks. Annals of Applied Probability, Vol. 14 (2004), 621-650.","journal-title":"Annals of Applied Probability"},{"key":"e_1_2_1_10_1","volume-title":"1995 a. Analysis of Parallel Processing Systems via the (max,+) Algebra","author":"Baccelli F.","unstructured":"F. Baccelli, B. Gaujal, A. Jean-Marie, and J. Mairesse. 1995 a. Analysis of Parallel Processing Systems via the (max,+) Algebra. Springer, Heidelberg, Germany, 69-98."},{"key":"e_1_2_1_11_1","volume-title":"1995 b. Quantitative Methods in Parallel Systems","author":"Baccelli F.","unstructured":"F. Baccelli, A. Jean-Marie, and I. Mitrani. 1995 b. Quantitative Methods in Parallel Systems. Springer, Heidelberg, Germany."},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1145\/77600.77622","article-title":"On the Execution of Parallel Programs on Multiprocessor Systems - A Queueing Theory Approach","volume":"32","author":"Baccelli F.","year":"1990","unstructured":"F. Baccelli and Z. Liu. 1990. On the Execution of Parallel Programs on Multiprocessor Systems - A Queueing Theory Approach. J. ACM, Vol. 32 (1990), 373-414.","journal-title":"J. ACM"},{"key":"e_1_2_1_13_1","first-page":"577","volume-title":"Energy Efficient Allocation of Virtual Machines in Cloud Data Centers. In 2010 10th IEEE\/ACM International Conference on Cluster, Cloud and Grid Computing. IEEE","author":"Beloglazov A.","unstructured":"A. Beloglazov and R. Buyya. 2010. Energy Efficient Allocation of Virtual Machines in Cloud Data Centers. In 2010 10th IEEE\/ACM International Conference on Cluster, Cloud and Grid Computing. IEEE, New York, USA, 577-578."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1017\/apr.2019.45"},{"key":"e_1_2_1_15_1","volume-title":"ACM TOMACS","volume":"25","author":"Blanchet J.","year":"2015","unstructured":"J. Blanchet and A. Wallwater. 2015. Exact sampling of stationary and time-reversed queues. ACM TOMACS, Vol. 25 (2015), 27 pages."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1214\/08-PS137"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.30.1.51"},{"key":"e_1_2_1_18_1","unstructured":"T. H. Cormen C. E. Leiserson R. L. Rivest and C. Stein. 2009. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill New York USA."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.mcm.2006.06.007"},{"key":"e_1_2_1_20_1","first-page":"1","volume-title":"Proceedings of the 5th Workshop on Advanced Tools, Programming Languages, and PLatforms for Implementing and Evaluating Algorithms for Distributed Systems. Association for Computing Machinery","author":"Grosof I.","unstructured":"I. Grosof and M. Harchol-Balter. 2023. Invited Paper: ServerFilling: A Better Approach to Packing Multiserver Jobs. In Proceedings of the 5th Workshop on Advanced Tools, Programming Languages, and PLatforms for Implementing and Evaluating Algorithms for Distributed Systems. Association for Computing Machinery, New York, USA, 1-5."},{"key":"e_1_2_1_21_1","unstructured":"I. Grosof M. Harchol-Balter and A. Scheller-Wolf. 2020. Stability for Two-class Multiserver-job Systems. arXiv preprint: 2010.00631."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626570.3626574"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2023.102378"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3570612"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11134-022-09762-x"},{"key":"e_1_2_1_26_1","first-page":"3","article-title":"Architecture of the Slurm Workload Manager. In Job Scheduling Strategies for Parallel Processing. Springer Nature Switzerland, Cham","author":"Jette M. A.","year":"2023","unstructured":"M. A. Jette and T. Wickberg. 2023. Architecture of the Slurm Workload Manager. In Job Scheduling Strategies for Parallel Processing. Springer Nature Switzerland, Cham, Switzerland, 3-23.","journal-title":"Switzerland"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1017\/S0305004100036781","article-title":"The stability of a queue with non-independent inter-arrival and service times","volume":"58","author":"Loynes R. M.","year":"1962","unstructured":"R. M. Loynes. 1962. The stability of a queue with non-independent inter-arrival and service times. Mathematical Proceedings of the Cambridge Philosophical Society, Vol. 58 (1962), 497-520.","journal-title":"Mathematical Proceedings of the Cambridge Philosophical Society"},{"key":"e_1_2_1_28_1","first-page":"702","article-title":"Stochastic models of load balancing and scheduling in cloud computing clusters. In IEEE INFOCOM. IEEE","author":"Maguluri S. T.","year":"2012","unstructured":"S. T. Maguluri, R. Srikant, and L. Ying. 2012. Stochastic models of load balancing and scheduling in cloud computing clusters. In IEEE INFOCOM. IEEE, New York, USA, 702-710.","journal-title":"New York, USA"},{"key":"e_1_2_1_29_1","first-page":"63","article-title":"Stability Analysis of a MAP\/M\/s Cluster Model by Matrix-Analytic Method. In EPEW. Springer","author":"Morozov E.","year":"2016","unstructured":"E. Morozov and A. S. Rumyantsev. 2016. Stability Analysis of a MAP\/M\/s Cluster Model by Matrix-Analytic Method. In EPEW. Springer, New York, USA, 63-76.","journal-title":"New York, USA"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.932708"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","first-page":"102370","DOI":"10.1016\/j.peva.2023.102370","article-title":"The saturated Multiserver Job Queuing Model with two classes of jobs: Exact and approximate results","volume":"162","author":"Olliaro D.","year":"2023","unstructured":"D. Olliaro, M. Ajmone Marsan, S. Balsamo, and A. Marin. 2023. The saturated Multiserver Job Queuing Model with two classes of jobs: Exact and approximate results. Performance Evaluation, Vol. 162 (2023), 102370.","journal-title":"Performance Evaluation"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2024.3497792"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/s10479-015-1917-2","article-title":"Stability criterion of a multiserver model with simultaneous service","volume":"252","author":"Rumyantsev A.","year":"2017","unstructured":"A. Rumyantsev and E. Morozov. 2017. Stability criterion of a multiserver model with simultaneous service. Annals of Operational Research, Vol. 252 (2017), 29-39.","journal-title":"Annals of Operational Research"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","unstructured":"A. Shehabi S. J. Smith A. Hubbard A. Newkirk N. Lei M. A. Siddik B. Holecek J. Koomey E. Masanet and D. Sartor. 2024. 2024 United States Data Center Energy Usage Report. Report. Berkeley Lab - Energy Analysis & Environmental Impacts Division. https:\/\/doi.org\/10.71468\/P1WC7Q","DOI":"10.71468\/P1WC7Q"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSC.2010.25"},{"key":"e_1_2_1_36_1","first-page":"1","article-title":"Borg: the next generation. In ACM EuroSys. Association for Computing Machinery","author":"Tirmazi M.","year":"2020","unstructured":"M. Tirmazi, A. Barker, N. Deng, M. E. Haque, Z. G. Qin, S. Hand, M. Harchol-Balter, and J. Wilkes. 2020. Borg: the next generation. In ACM EuroSys. Association for Computing Machinery, New York, USA, 1-14.","journal-title":"New York, USA"},{"key":"e_1_2_1_37_1","first-page":"1","article-title":"Apache Hadoop YARN: yet another resource negotiator. In ACM SOCC. ACM","author":"Vavilapalli V. K.","year":"2013","unstructured":"V. K. Vavilapalli, A. C. Murthy, C. Douglas, S. Agarwal, M. Konar, R. Evans, T. Graves, J. Lowe, H. Shah, S. Seth, B. Saha, C. Curino, O. O'Malley, S. Radia, B. Reed, and E. Baldeschwieler. 2013. Apache Hadoop YARN: yet another resource negotiator. In ACM SOCC. ACM, New York, USA, 1-16.","journal-title":"New York, USA"},{"key":"e_1_2_1_38_1","first-page":"143","volume-title":"Data-Driven Workload Generation Based on Google Data Center Measurements. In 2024 IEEE 25th International Conference on High Performance Switching and Routing (HPSR). IEEE","author":"Yildiz M.","unstructured":"M. Yildiz and A. Baiocchi. 2024. Data-Driven Workload Generation Based on Google Data Center Measurements. In 2024 IEEE 25th International Conference on High Performance Switching and Routing (HPSR). IEEE, New York, USA, 143-148."}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3788105","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T18:50:31Z","timestamp":1774551031000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3788105"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,26]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,3,26]]}},"alternative-id":["10.1145\/3788105"],"URL":"https:\/\/doi.org\/10.1145\/3788105","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,26]]},"assertion":[{"value":"2026-03-26","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}