{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T16:39:10Z","timestamp":1780591150919,"version":"3.54.1"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,5,21]],"date-time":"2024-05-21T00:00:00Z","timestamp":1716249600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"the Netherlands Organization for Scientific Research (NWO) through Gravitation","award":["NETWORKS-024.002.003"],"award-info":[{"award-number":["NETWORKS-024.002.003"]}]},{"name":"VICI","award":["202.068"],"award-info":[{"award-number":["202.068"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2024,5,21]]},"abstract":"<jats:p>The present paper establishes an explicit multi-dimensional state space collapse (SSC) for parallel-processing systems with arbitrary compatibility constraints between servers and job types. This breaks major new ground beyond the SSC results and queue length asymptotics in the literature which are largely restricted to complete resource pooling (CRP) scenarios where the steady-state queue length vector concentrates around a line in heavy traffic. The multi-dimensional SSC that we establish reveals heavy-traffic behavior which is also far more tractable than the pre-limit queue length distribution, yet exhibits a fundamentally more intricate structure than in the one-dimensional case, providing useful insight into the system dynamics. In particular, we prove that the limiting queue length vector lives in a K-dimensional cone of which the set of spanning vectors is random in general, capturing the delicate interplay between the various job types and servers. For a broad class of systems we provide a further simplification which shows that the collection of random cones constitutes a fixed K-dimensional cone, resulting in a K-dimensional SSC. The dimension~K represents the number of critically loaded subsystems, or equivalently, capacity bottlenecks in heavy-traffic, with K=1 corresponding to conventional CRP scenarios. Our approach leverages probability generating function (PGF) expressions for Markovian systems operating under redundancy policies.<\/jats:p>","DOI":"10.1145\/3656016","type":"journal-article","created":{"date-parts":[[2024,5,29]],"date-time":"2024-05-29T10:40:32Z","timestamp":1716979232000},"page":"1-52","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Multi-dimensional State Space Collapse in Non-complete Resource Pooling Scenarios"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1350-9346","authenticated-orcid":false,"given":"Ellen","family":"Cardinaels","sequence":"first","affiliation":[{"name":"Eindhoven University of Technology, Eindhoven, Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3306-6447","authenticated-orcid":false,"given":"Sem","family":"Borst","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology, Eindhoven, Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9752-0018","authenticated-orcid":false,"given":"Johan S.H.","family":"van Leeuwaarden","sequence":"additional","affiliation":[{"name":"Tilburg University, Tilburg, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,5,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2018.10.005"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1287\/13-SSY117"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2020.2027"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428333"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11134-019-09605-2"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2019.1851"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2018.09.008"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1015345343"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1214\/EJP.v10-281"},{"key":"e_1_2_1_10_1","volume-title":"State space collapse with application to heavy traffic limits for multiclass queueing networks. Queueing Sys., 30(1--2):89--148","author":"Bramson M.","year":"1998","unstructured":"M. Bramson. State space collapse with application to heavy traffic limits for multiclass queueing networks. Queueing Sys., 30(1--2):89--148, 1998."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2022.2385"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1080\/15326349.2021.1962352"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1214\/08-AAP522"},{"key":"e_1_2_1_14_1","volume-title":"Asymptotically tight steady-state queue length bounds implied by drift conditions. Queueing Syst., 72(3--4):311--359","author":"Eryilmaz A.","year":"2012","unstructured":"A. Eryilmaz and R. Srikant. Asymptotically tight steady-state queue length bounds implied by drift conditions. Queueing Syst., 72(3--4):311--359, 2012."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1019175812444"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2017.07.001"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11134-020-09668-6"},{"key":"e_1_2_1_18_1","volume-title":"Queueing with redundant requests: Exact analysis. Queueing Syst., 83(3--4):227--259","author":"Gardner K.","year":"2016","unstructured":"K. Gardner, S. Zbarsky, S. Doroudi, M. Harchol-Balter, E. Hyyti\u00e4, and A. Scheller-Wolf. Queueing with redundant requests: Exact analysis. Queueing Syst., 83(3--4):227--259, 2016."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1028903452"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1019188531950"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.2139\/ssrn.4405218"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3374888.3374902"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1287\/stsy.2019.0056"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2021.1248"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-51431-9"},{"key":"e_1_2_1_26_1","volume-title":"Heavy traffic joint queue length distribution without resource pooling","author":"Jhunjhunwala P. R.","year":"2022","unstructured":"P. R. Jhunjhunwala and S. T. Maguluri. Heavy traffic joint queue length distribution without resource pooling. 2022. arXiv: 2206.06504."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3595244.3595254"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1214\/08-AAP591"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01158929"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100036094"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1962.tb00465.x"},{"key":"e_1_2_1_32_1","first-page":"85","volume-title":"R","author":"Krzesinski A. E.","year":"2011","unstructured":"A. E. Krzesinski. Order independent queues. In R. Boucherie and N. van Dijk, editors, Queueing Networks. International Series in Operations Research and Management Science, volume 154, pages 85--120. Springer, Boston, MA, 2011."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.2307\/1427485"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.9.3.383"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1040.0152"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/1830479"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1214\/13-AAP970"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1075828046"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0269964805050096"},{"key":"e_1_2_1_40_1","volume-title":"Transportation polytope and its applications in parallel server systems","author":"Varma S. M.","year":"2021","unstructured":"S. M. Varma and S. T. Maguluri. Transportation polytope and its applications in parallel server systems. 2021. arXiv: 2108.13167."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11134-011-9274-6"},{"key":"e_1_2_1_42_1","volume-title":"Insensitivity of proportional fairness in critically loaded bandwidth sharing networks","author":"Vlasiou M.","year":"2021","unstructured":"M. Vlasiou, J. Zhang, and B. Zwart. Insensitivity of proportional fairness in critically loaded bandwidth sharing networks. 2021. arXiv: 1411.4841."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2021.1225"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1019108819713"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1090\/fic\/028\/03"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3656016","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3656016","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,23]],"date-time":"2025-08-23T18:02:27Z","timestamp":1755972147000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3656016"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,21]]},"references-count":45,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,5,21]]}},"alternative-id":["10.1145\/3656016"],"URL":"https:\/\/doi.org\/10.1145\/3656016","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,21]]},"assertion":[{"value":"2024-05-29","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}