{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,16]],"date-time":"2026-01-16T01:46:08Z","timestamp":1768527968759,"version":"3.49.0"},"reference-count":15,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2015,11,19]],"date-time":"2015-11-19T00:00:00Z","timestamp":1447891200000},"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":[[2015,11,19]]},"abstract":"<jats:p>In cloud computing jobs consisting of many tasks run in parallel, the tasks on the slowest machines (straggling tasks) become the bottleneck in the completion of the job. One way to combat the variability in machine response time is to add replicas of straggling tasks and wait for the earliest copy to finish. Using the theory of extreme order statistics, we analyze how task replication reduces latency, and its impact on the cost of computing resources. We also propose a heuristic algorithm to search for the best replication strategies when it is difficult to model the empirical behavior of task execution time and use the proposed analysis techniques. Evaluation of the heuristic policies on Google Trace data shows a significant latency reduction compared to the replication strategy used in MapReduce.<\/jats:p>","DOI":"10.1145\/2847220.2847223","type":"journal-article","created":{"date-parts":[[2015,11,20]],"date-time":"2015-11-20T13:58:34Z","timestamp":1448027914000},"page":"7-11","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":100,"title":["Using Straggler Replication to Reduce Latency in Large-scale Parallel Computing"],"prefix":"10.1145","volume":"43","author":[{"given":"Da","family":"Wang","sequence":"first","affiliation":[{"name":"Two Sigma Investments, New York, NY"}]},{"given":"Gauri","family":"Joshi","sequence":"additional","affiliation":[{"name":"MIT, Cambridge, MA"}]},{"given":"Gregory","family":"Wornell","sequence":"additional","affiliation":[{"name":"MIT, Cambridge, MA"}]}],"member":"320","published-online":{"date-parts":[[2015,11,19]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Google cluster data. http:\/\/code.google.com\/p\/googleclusterdata\/.  Google cluster data. http:\/\/code.google.com\/p\/googleclusterdata\/."},{"key":"e_1_2_1_2_1","first-page":"185","volume-title":"USENIX NSDI","author":"Ananthanarayanan G.","year":"2013"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"David H. A. and Nagaraja H. N. Order statistics. John Wiley Hoboken N.J. 2003.  David H. A. and Nagaraja H. N. Order statistics. John Wiley Hoboken N.J. 2003.","DOI":"10.1002\/0471722162"},{"key":"e_1_2_1_4_1","volume-title":"Springer","author":"de Haan L.","year":"2006"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/11407522_15"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2408776.2408794"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Joshi G. Liu Y. and Soljanin E. On the Delay-Storage Trade-o? in Content Download from Coded Distributed Storage Systems. IEEE JSAC (May 2014) 989--997.  Joshi G. Liu Y. and Soljanin E. On the Delay-Storage Trade-o? in Content Download from Coded Distributed Storage Systems. IEEE JSAC (May 2014) 989--997.","DOI":"10.1109\/JSAC.2014.140518"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2825236.2825258"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1002\/1520-6750(198712)34:6<823::AID-NAV3220340607>3.0.CO;2-R"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522716"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535372.2535392"},{"key":"e_1_2_1_14_1","volume-title":"Massachusetts Institute of Technology","author":"Wang D.","year":"2014"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2637364.2592042"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Wang D. Joshi G. and Wornell G. Using straggler replication to reduce latency in large-scale parallel computing (extended version). arXiv:1503.03128 {cs.dc} (Mar. 2015).  Wang D. Joshi G. and Wornell G. Using straggler replication to reduce latency in large-scale parallel computing (extended version). arXiv:1503.03128 {cs.dc} (Mar. 2015).","DOI":"10.1145\/2847220.2847223"}],"container-title":["ACM SIGMETRICS Performance Evaluation Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2847220.2847223","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2847220.2847223","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:48:23Z","timestamp":1750225703000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2847220.2847223"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,11,19]]},"references-count":15,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,11,19]]}},"alternative-id":["10.1145\/2847220.2847223"],"URL":"https:\/\/doi.org\/10.1145\/2847220.2847223","relation":{},"ISSN":["0163-5999"],"issn-type":[{"value":"0163-5999","type":"print"}],"subject":[],"published":{"date-parts":[[2015,11,19]]},"assertion":[{"value":"2015-11-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}