{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,26]],"date-time":"2026-08-26T04:07:01Z","timestamp":1787717221714,"version":"build-2784847793"},"reference-count":8,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2014,1,10]],"date-time":"2014-01-10T00:00:00Z","timestamp":1389312000000},"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":[[2014,1,10]]},"abstract":"<jats:p>MapReduce is a scalable parallel computing framework for big data processing. It exhibits multiple processing phases, and thus an efficient job scheduling mechanism is crucial for ensuring efficient resource utilization. This work studies the scheduling challenge that results from the overlapping of the \"map\" and \"shuffle\" phases in MapReduce. We propose a new, general model for this scheduling problem. Further, we prove that scheduling to minimize average response time in this model is strongly NP-hard in the offline case and that no online algorithm can be constant-competitive in the online case. However, we provide two online algorithms that match the performance of the offline optimal when given a slightly faster service rate.<\/jats:p>","DOI":"10.1145\/2567529.2567534","type":"journal-article","created":{"date-parts":[[2014,1,21]],"date-time":"2014-01-21T13:31:00Z","timestamp":1390311060000},"page":"16-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Joint optimization of overlapping phases in MapReduce"],"prefix":"10.1145","volume":"41","author":[{"given":"Minghong","family":"Lin","sequence":"first","affiliation":[{"name":"Computer Science, California Institute of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Li","family":"Zhang","sequence":"additional","affiliation":[{"name":"IBM T.J. Watson Research Center"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Adam","family":"Wierman","sequence":"additional","affiliation":[{"name":"Computer Science, California Institute of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jian","family":"Tan","sequence":"additional","affiliation":[{"name":"IBM T.J. Watson Research Center"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,1,10]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Fair Scheduler http:\/\/hadoop.apache.org\/mapreduce\/docs\/r0.21.0\/fair_scheduler.html.  Fair Scheduler http:\/\/hadoop.apache.org\/mapreduce\/docs\/r0.21.0\/fair_scheduler.html."},{"key":"e_1_2_1_2_1","unstructured":"Capacity Scheduler http:\/\/hadoop.apache.org\/mapreduce\/docs\/r0.21.0\/capacity_scheduler.html.  Capacity Scheduler http:\/\/hadoop.apache.org\/mapreduce\/docs\/r0.21.0\/capacity_scheduler.html."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_2_1_4_1","volume-title":"Elsevier","author":"Graham R.","year":"1979"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1272996.1273005"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCGRID.2010.112"},{"key":"e_1_2_1_7_1","volume-title":"Wiley","author":"van Dijk N. M.","year":"1993"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of OSDI","author":"Zaharia M.","year":"2008"}],"container-title":["ACM SIGMETRICS Performance Evaluation Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2567529.2567534","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2567529.2567534","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:34:38Z","timestamp":1750232078000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2567529.2567534"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1,10]]},"references-count":8,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,1,10]]}},"alternative-id":["10.1145\/2567529.2567534"],"URL":"https:\/\/doi.org\/10.1145\/2567529.2567534","relation":{},"ISSN":["0163-5999"],"issn-type":[{"value":"0163-5999","type":"print"}],"subject":[],"published":{"date-parts":[[2014,1,10]]},"assertion":[{"value":"2014-01-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}