{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:12:38Z","timestamp":1750219958253,"version":"3.41.0"},"reference-count":14,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,4,26]],"date-time":"2023-04-26T00:00:00Z","timestamp":1682467200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMETRICS Perform. Eval. Rev."],"published-print":{"date-parts":[[2023,4,26]]},"abstract":"<jats:p>We consider (k, k) fork-join scheduling on a large number (say, N) of parallel servers with two sets of heterogeneous rates. An incoming task is split into k sub-tasks and dispatched to k servers according to a probabilistic selection policy, with parameter ps being the selection probability of slower servers. Mean task completion time admits an integral form, and thus it is analytically intractable to compute ps that minimizes it. In this work, we provide an upper bound on the mean task completion time, and determine ps that minimizes this upper bound. Numerically, this choice has been shown to be near-optimal.<\/jats:p>","DOI":"10.1145\/3595244.3595248","type":"journal-article","created":{"date-parts":[[2023,4,27]],"date-time":"2023-04-27T10:27:14Z","timestamp":1682591234000},"page":"8-10","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Asymptotic Analysis of Probabilistic Scheduling for Erasure-Coded Heterogeneous Systems"],"prefix":"10.1145","volume":"50","author":[{"given":"Rooji","family":"Jinan","sequence":"first","affiliation":[{"name":"Indian Institute of Science, Bangalore 560012, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gaurav","family":"Gautam","sequence":"additional","affiliation":[{"name":"Indian Institute of Science, Bangalore 560012, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Parimal","family":"Parag","sequence":"additional","affiliation":[{"name":"Indian Institute of Science, Bangalore 560012, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vaneet","family":"Aggarwal","sequence":"additional","affiliation":[{"name":"Purdue University, West Lafayette, IN, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,4,27]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3305218.3305228"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/306902.306921"},{"key":"e_1_2_1_3_1","volume-title":"Operations Research","author":"Gardner K.","year":"2017","unstructured":"K. Gardner , M. Harchol-Balter , A. Scheller-Wolf , M. Velednitsky , and S. Zbarsky . Redundancy-d: The power of d choices for redundancy . Operations Research , Aug. 2017 . K. Gardner, M. Harchol-Balter, A. Scheller-Wolf, M. Velednitsky, and S. Zbarsky. Redundancy-d: The power of d choices for redundancy. Operations Research, Aug. 2017."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2020.102151"},{"key":"e_1_2_1_5_1","volume-title":"May","author":"Goren G.","year":"2021","unstructured":"G. Goren , S. Vargaftik , and Y. Moses . Stochastic coordination in heterogeneous load balancing systems. arXiv preprint arXiv:2105.09389 , May 2021 . G. Goren, S. Vargaftik, and Y. Moses. Stochastic coordination in heterogeneous load balancing systems. arXiv preprint arXiv:2105.09389, May 2021."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/2462638"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3224422"},{"key":"e_1_2_1_8_1","volume-title":"A general \"power-of-d\" dispatching framework for heterogeneous systems","author":"Jaleel J. A.","year":"2021","unstructured":"J. A. Jaleel , S. Doroudi , K. Gardner , and A. Wickeham . A general \"power-of-d\" dispatching framework for heterogeneous systems , 2021 . J. A. Jaleel, S. Doroudi, K. Gardner, and A. Wickeham. A general \"power-of-d\" dispatching framework for heterogeneous systems, 2021."},{"key":"e_1_2_1_9_1","volume-title":"Load balancing policies with server-side cancellation of replicas. arXiv preprint arXiv:2010.13575","author":"Jinan R.","year":"2020","unstructured":"R. Jinan , A. Badita , T. Bodas , and P. Parag . Load balancing policies with server-side cancellation of replicas. arXiv preprint arXiv:2010.13575 , 2020 . R. Jinan, A. Badita, T. Bodas, and P. Parag. Load balancing policies with server-side cancellation of replicas. arXiv preprint arXiv:2010.13575, 2020."},{"key":"e_1_2_1_10_1","volume-title":"Oct.","author":"Mitzenmacher M.","year":"2001","unstructured":"M. Mitzenmacher . The power of two choices in randomized load balancing. 12(10):1094--1104 , Oct. 2001 . M. Mitzenmacher. The power of two choices in randomized load balancing. 12(10):1094--1104, Oct. 2001."},{"key":"e_1_2_1_11_1","volume-title":"Large-scale parallel server system with multi-component jobs. arXiv preprint arXiv:2006.11256","author":"Shneer S.","year":"2020","unstructured":"S. Shneer and A. Stolyar . Large-scale parallel server system with multi-component jobs. arXiv preprint arXiv:2006.11256 , 2020 . S. Shneer and A. Stolyar. Large-scale parallel server system with multi-component jobs. arXiv preprint arXiv:2006.11256, 2020."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/IWQOS52092.2021.9521355"},{"issue":"1","key":"e_1_2_1_13_1","first-page":"20","article-title":"Queueing system with selection of the shortest of two queues: An asymptotic approach","volume":"32","author":"Vvedenskaya N. D.","year":"1996","unstructured":"N. D. Vvedenskaya , R. L. Dobrushin , and F. I. Karpelevich . Queueing system with selection of the shortest of two queues: An asymptotic approach . Problemy Peredachi Informatsii , 32 ( 1 ): 20 -- 34 , 1996 . N. D. Vvedenskaya, R. L. Dobrushin, and F. I. Karpelevich. Queueing system with selection of the shortest of two queues: An asymptotic approach. Problemy Peredachi Informatsii, 32(1):20--34, 1996.","journal-title":"Problemy Peredachi Informatsii"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.2307\/3213271"}],"container-title":["ACM SIGMETRICS Performance Evaluation Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3595244.3595248","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3595244.3595248","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:49:08Z","timestamp":1750182548000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3595244.3595248"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,26]]},"references-count":14,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,4,26]]}},"alternative-id":["10.1145\/3595244.3595248"],"URL":"https:\/\/doi.org\/10.1145\/3595244.3595248","relation":{},"ISSN":["0163-5999"],"issn-type":[{"type":"print","value":"0163-5999"}],"subject":[],"published":{"date-parts":[[2023,4,26]]},"assertion":[{"value":"2023-04-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}