{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:20:45Z","timestamp":1750220445408,"version":"3.41.0"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,5,25]],"date-time":"2021-05-25T00:00:00Z","timestamp":1621900800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science Foundation","award":["CNS-1717060, IIS-0916440, ECCS-1232118, and SES-1409214"],"award-info":[{"award-number":["CNS-1717060, IIS-0916440, ECCS-1232118, and SES-1409214"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2021,6,30]]},"abstract":"<jats:p>\n            Parallel and distributed computing systems are foundational to the success of cloud computing and big data analytics. These systems process computational workflows in a way that can be mathematically modeled by a fork-and-join queueing network with blocking (FJQN\/B). While engineering solutions have long been made to build and scale such systems, it is challenging to rigorously characterize their throughput performance at scale theoretically. What further complicates the study is the presence of heavy-tailed delays that have been widely documented therein. In this article, we utilize an infinite sequence of FJQN\/Bs to study the throughput limit and focus on an important class of heavy-tailed service times that are regularly varying with index\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            . The throughput is said to be scalable if the throughput limit infimum of the sequence is strictly positive as the network size grows to infinity. We introduce two novel geometric concepts\u2014scaling dimension and extended metric dimension\u2014and show that an infinite sequence of FJQN\/Bs is throughput scalable if the extended metric dimension\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            and only if the scaling dimension\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            . We also show that for the cases where buffer sizes are scaling in an order of\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            , the scalability conditions are relaxed by a factor of\u00a0\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            . The results provide new insights on the scalability of a rich class of FJQN\/Bs with various structures, including tandem, lattice, hexagon, pyramid, tree, and fractals.\n          <\/jats:p>","DOI":"10.1145\/3448213","type":"journal-article","created":{"date-parts":[[2021,5,25]],"date-time":"2021-05-25T13:03:39Z","timestamp":1621947819000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Fork and Join Queueing Networks with Heavy Tails: Scaling Dimension and Throughput Limit"],"prefix":"10.1145","volume":"68","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7246-251X","authenticated-orcid":false,"given":"Yun","family":"Zeng","sequence":"first","affiliation":[{"name":"Amazon.com, Inc., Seattle, WA, USA"}]},{"given":"Jian","family":"Tan","sequence":"additional","affiliation":[{"name":"Alibaba Group, Sunnyvale, CA, USA"}]},{"given":"Cathy H.","family":"Xia","sequence":"additional","affiliation":[{"name":"The Ohio State University, Columbus, OH, USA"}]}],"member":"320","published-online":{"date-parts":[[2021,5,25]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"[n.d.]. Amazon AWS. Retrieved from https:\/\/aws.amazon.com\/.  [n.d.]. Amazon AWS. Retrieved from https:\/\/aws.amazon.com\/."},{"key":"e_1_2_1_2_1","unstructured":"[n.d.]. Google Cloud. Retrieved from https:\/\/cloud.google.com\/.  [n.d.]. Google Cloud. Retrieved from https:\/\/cloud.google.com\/."},{"key":"e_1_2_1_3_1","unstructured":"[n.d.]. IBM BlueMix. Retrieved from https:\/\/www.ibm.com\/cloud\/.  [n.d.]. IBM BlueMix. Retrieved from https:\/\/www.ibm.com\/cloud\/."},{"key":"e_1_2_1_4_1","unstructured":"[n.d.]. Microsoft Azure. Retrieved from https:\/\/azure.microsoft.com\/.  [n.d.]. Microsoft Azure. Retrieved from https:\/\/azure.microsoft.com\/."},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM\u201905)","volume":"3","author":"Baccelli F.","unstructured":"F. Baccelli , A. Chaintreau , Z. Liu , and A. Riabov . 2005. The one-to-many TCP overlay: A scalable and reliable multicast architecture . In Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM\u201905) . Vol. 3 . IEEE, 1629\u20131640. F. Baccelli, A. Chaintreau, Z. Liu, and A. Riabov. 2005. The one-to-many TCP overlay: A scalable and reliable multicast architecture. In Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM\u201905). Vol. 3. IEEE, 1629\u20131640."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.2307\/1427772"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/9.182477"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"N. H. Bingham C. M. Goldie and J. L. Teugels. 1987. Regular Variation. Cambridge University Press.  N. H. Bingham C. M. Goldie and J. L. Teugels. 1987. Regular Variation. Cambridge University Press.","DOI":"10.1017\/CBO9780511721434"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69355-0_8"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(00)00198-0"},{"volume-title":"Proceedings of the 2016 IEEE 2nd International Conference on Multimedia Big Data (BigMM\u201916)","author":"Chen N.","key":"e_1_2_1_12_1","unstructured":"N. Chen , Y. Chen , Y. You , H. Ling , P. Liang , and R. Zimmermann . 2016. Dynamic urban surveillance video stream processing using fog computing . In Proceedings of the 2016 IEEE 2nd International Conference on Multimedia Big Data (BigMM\u201916) . IEEE, 105\u2013112. N. Chen, Y. Chen, Y. You, H. Ling, P. Liang, and R. Zimmermann. 2016. Dynamic urban surveillance video stream processing using fog computing. In Proceedings of the 2016 IEEE 2nd International Conference on Multimedia Big Data (BigMM\u201916). IEEE, 105\u2013112."},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"S. Coles J. Bawa L. Trenner and P. Dorazio. 2001. An Introduction to Statistical Modeling of Extreme Values. Vol. 208. Springer London.  S. Coles J. Bawa L. Trenner and P. Dorazio. 2001. An Introduction to Statistical Modeling of Extreme Values. Vol. 208. Springer London.","DOI":"10.1007\/978-1-4471-3675-0"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177005277"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2011.12.009"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/185675.185776"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/70.611303"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2016.245"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2408776.2408794"},{"key":"e_1_2_1_20_1","article-title":"Hausdorff and spectral dimension of infinite random graphs","volume":"40","author":"Durhuus B.","year":"2009","unstructured":"B. Durhuus . 2009 . Hausdorff and spectral dimension of infinite random graphs . Acta Phys. Polon. B 40 , 12 (2009). B. Durhuus. 2009. Hausdorff and spectral dimension of infinite random graphs. Acta Phys. Polon. B 40, 12 (2009).","journal-title":"Acta Phys. Polon. B"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/262578"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comcom.2015.09.006"},{"key":"e_1_2_1_23_1","volume-title":"Fractal Geometry: Mathematical Foundations and Applications","author":"Falconer K.","year":"2004","unstructured":"K. Falconer . 2004 . Fractal Geometry: Mathematical Foundations and Applications . John Wiley & Sons . K. Falconer. 2004. Fractal Geometry: Mathematical Foundations and Applications. John Wiley & Sons."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/839293.843229"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/578533"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/2781928.2782616"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142522"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2007.892846"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCGRID.2010.112"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(95)00106-2"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742788"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2015.0740"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1287\/15-SSY206"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1015729701521"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-4149(01)00142-9"},{"key":"e_1_2_1_36_1","first-page":"273","article-title":"Last-passage percolation with general weight distribution","volume":"12","author":"Martin J. B.","year":"2006","unstructured":"J. B. Martin . 2006 . Last-passage percolation with general weight distribution . Markov Process. Relat. Fields 12 , 2 (2006), 273 \u2013 299 . J. B. Martin. 2006. Last-passage percolation with general weight distribution. Markov Process. Relat. Fields 12, 2 (2006), 273\u2013299.","journal-title":"Markov Process. Relat. Fields"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1101\/gr.107524.110"},{"volume-title":"Subexponentiality and Their Applications in Probability Theory","author":"Mikosch T.","key":"e_1_2_1_38_1","unstructured":"T. Mikosch . 1999. Regular Variation , Subexponentiality and Their Applications in Probability Theory . Eindhoven University of Technology . T. Mikosch. 1999. Regular Variation, Subexponentiality and Their Applications in Probability Theory. Eindhoven University of Technology."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCC.2014.22"},{"key":"e_1_2_1_40_1","volume-title":"Scale: Google Trace Analysis. Technical Report","author":"Reiss C.","year":"2012","unstructured":"C. Reiss , A. Tumanov , G. R. Ganger , R. H. Katz , and M. A. Kozuch . 2012 . Towards Understanding Heterogeneous Clouds at Scale: Google Trace Analysis. Technical Report , Intel Science and Technology Center for Cloud Computing ( 2012). C. Reiss, A. Tumanov, G. R. Ganger, R. H. Katz, and M. A. Kozuch. 2012. Towards Understanding Heterogeneous Clouds at Scale: Google Trace Analysis. Technical Report, Intel Science and Technology Center for Cloud Computing (2012)."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0219887806001156"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11134-016-9486-x"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2318857.2254761"},{"volume-title":"Proceedings of the International Conference on Analytical and Stochastic Modeling Techniques and Applications. Springer","author":"Tancrez J. S.","key":"e_1_2_1_44_1","unstructured":"J. S. Tancrez , P. Chevalier , and P. Semal . 2013. A tight bound on the throughput of queueing networks with blocking . In Proceedings of the International Conference on Analytical and Stochastic Modeling Techniques and Applications. Springer , Berlin, 396\u2013415. J. S. Tancrez, P. Chevalier, and P. Semal. 2013. A tight bound on the throughput of queueing networks with blocking. In Proceedings of the International Conference on Analytical and Stochastic Modeling Techniques and Applications. Springer, Berlin, 396\u2013415."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2628913"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-5316(94)90016-7"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2847220.2847223"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCC.2015.14"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1269899.1254898"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/GRID.2004.47"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2964791.2901470"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2015.06.007"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3448213","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3448213","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3448213","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:47:40Z","timestamp":1750193260000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3448213"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,25]]},"references-count":51,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,6,30]]}},"alternative-id":["10.1145\/3448213"],"URL":"https:\/\/doi.org\/10.1145\/3448213","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2021,5,25]]},"assertion":[{"value":"2018-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-05-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}