{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T15:43:26Z","timestamp":1772725406627,"version":"3.50.1"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,9,12]],"date-time":"2019-09-12T00:00:00Z","timestamp":1568246400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100008952","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-16-CE25-0014-01"],"award-info":[{"award-number":["ANR-16-CE25-0014-01"]}],"id":[{"id":"10.13039\/501100008952","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Model. Perform. Eval. Comput. Syst."],"published-print":{"date-parts":[[2019,9,30]]},"abstract":"<jats:p>Big Data systems (e.g., Google MapReduce, Apache Hadoop, Apache Spark) rely increasingly on speculative execution to mask slow tasks, also known as stragglers, because a job\u2019s execution time is dominated by the slowest task instance. Big Data systems typically identify stragglers and speculatively run copies of those tasks with the expectation that a copy may complete faster to shorten job execution times. There is a rich body of recent results on straggler mitigation in MapReduce. However, the majority of these do not consider the problem of accurately detecting stragglers. Instead, they adopt a particular straggler detection approach and then study its effectiveness in terms of performance, e.g., reduction in job completion time or higher efficiency, e.g., high resource utilization. In this article, we consider a complete framework for straggler detection and mitigation. We start with a set of metrics that can be used to characterize and detect stragglers including Precision, Recall, Detection Latency, Undetected Time, and Fake Positive. We then develop an architectural model by which these metrics can be linked to measures of performance including execution time and system energy overheads. We further conduct a series of experiments to demonstrate which metrics and approaches are more effective in detecting stragglers and are also predictive of effectiveness in terms of performance and energy efficiencies. For example, our results indicate that the default Hadoop straggler detector could be made more effective. In a certain case, Precision is low and only 55% of those detected are actual stragglers and the Recall, i.e., percent of actual detected stragglers, is also relatively low at 56%. For the same case, the hierarchical approach (i.e., a green-driven detector based on the default one) achieves a Precision of 99% and a Recall of 29%. This increase in Precision can be translated to achieve lower execution time and energy consumption, and thus higher performance and energy efficiency; compared to the default Hadoop mechanism, the energy consumption is reduced by almost 31%. These results demonstrate how our framework can offer useful insights and be applied in practical settings to characterize and design new straggler detection mechanisms for MapReduce systems.<\/jats:p>","DOI":"10.1145\/3328740","type":"journal-article","created":{"date-parts":[[2019,9,13]],"date-time":"2019-09-13T12:28:56Z","timestamp":1568377736000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["A New Framework for Evaluating Straggler Detection Mechanisms in MapReduce"],"prefix":"10.1145","volume":"4","author":[{"given":"Tien-Dat","family":"Phan","sequence":"first","affiliation":[{"name":"Inria, Univ Rennes, CNRS, IRISA, Rennes, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guillaume","family":"Pallez","sequence":"additional","affiliation":[{"name":"Inria Bordeaux Sud-Ouest 8 University of Bordeaux, Talence, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4306-5280","authenticated-orcid":false,"given":"Shadi","family":"Ibrahim","sequence":"additional","affiliation":[{"name":"Inria, IMT Atlantique, LS2N, Rennes, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Padma","family":"Raghavan","sequence":"additional","affiliation":[{"name":"Vanderbilt University, Nashville, TN, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,9,12]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI\u201913)","author":"Ananthanarayanan Ganesh","year":"2013","unstructured":"Ganesh Ananthanarayanan , Ali Ghodsi , Scott Shenker , and Ion Stoica . 2013 . Effective straggler mitigation: Attack of the clones . In Proceedings of the 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI\u201913) . 185--198. Ganesh Ananthanarayanan, Ali Ghodsi, Scott Shenker, and Ion Stoica. 2013. Effective straggler mitigation: Attack of the clones. In Proceedings of the 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI\u201913). 185--198."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/1924943.1924962"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2013.10.010"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Daniel Balouek Alexandra Carpen Amarie Ghislain Charrier Fr\u00e9d\u00e9ric Desprez Emmanuel Jeannot Emmanuel Jeanvoine Adrien L\u00e8bre David Margery Nicolas Niclausse Lucas Nussbaum Olivier Richard Christian P\u00e9rez Flavien Quesnel Cyril Rohr and Luc Sarzyniec. 2013. Adding virtualization capabilities to the Grid\u20195000 testbed. In Cloud Computing and Services Science. Springer International Publishing.  Daniel Balouek Alexandra Carpen Amarie Ghislain Charrier Fr\u00e9d\u00e9ric Desprez Emmanuel Jeannot Emmanuel Jeanvoine Adrien L\u00e8bre David Margery Nicolas Niclausse Lucas Nussbaum Olivier Richard Christian P\u00e9rez Flavien Quesnel Cyril Rohr and Luc Sarzyniec. 2013. Adding virtualization capabilities to the Grid\u20195000 testbed. In Cloud Computing and Services Science. Springer International Publishing.","DOI":"10.1007\/978-3-319-04519-1_1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2013.15"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 3rd ACM SIGOPS International Workshop on Large Scale Distributed Systems and Middleware (LADIS\u201909)","author":"Dean Jeffrey","year":"2009","unstructured":"Jeffrey Dean . 2009 . Large-scale distributed systems at Google: Current systems and future directions . In Proceedings of the 3rd ACM SIGOPS International Workshop on Large Scale Distributed Systems and Middleware (LADIS\u201909) . Jeffrey Dean. 2009. Large-scale distributed systems at Google: Current systems and future directions. In Proceedings of the 3rd ACM SIGOPS International Workshop on Large Scale Distributed Systems and Middleware (LADIS\u201909)."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2012.107"},{"key":"e_1_2_1_9_1","unstructured":"HDFS. 2016. The Hadoop Distributed File System. Retrieved from https:\/\/hadoop.apache.org\/docs\/r2.7.3\/hadoop-project-dist\/hadoop-hdfs\/HdfsDesign.html.  HDFS. 2016. The Hadoop Distributed File System. Retrieved from https:\/\/hadoop.apache.org\/docs\/r2.7.3\/hadoop-project-dist\/hadoop-hdfs\/HdfsDesign.html."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCGrid.2012.122"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/CloudCom.2010.25"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Hai Jin Shadi Ibrahim Li Qi Haijun Cao Song Wu and Xuanhua Shi. 2011. The MapReduce programming model and implementations. In Cloud Comput.: Principles Paradigms. 373--390.  Hai Jin Shadi Ibrahim Li Qi Haijun Cao Song Wu and Xuanhua Shi. 2011. The MapReduce programming model and implementations. In Cloud Comput.: Principles Paradigms. 373--390.","DOI":"10.1002\/9780470940105.ch14"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSDIS.2015.45"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-64203-1_28"},{"key":"e_1_2_1_15_1","unstructured":"The Apache Hadoop Project. 2018. Retrieved from http:\/\/hadoop.apache.org.  The Apache Hadoop Project. 2018. Retrieved from http:\/\/hadoop.apache.org."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536206.2536213"},{"key":"e_1_2_1_18_1","volume-title":"Puma: Purdue MapReduce benchmarks suite. Technical Report","author":"Thottethodi M.","year":"2012","unstructured":"M. Thottethodi , F. Ahmad , S. Lee , and TN Vijaykumar . 2012 . Puma: Purdue MapReduce benchmarks suite. Technical Report , Purdue University . M. Thottethodi, F. Ahmad, S. Lee, and TN Vijaykumar. 2012. Puma: Purdue MapReduce benchmarks suite. Technical Report, Purdue University."},{"key":"e_1_2_1_19_1","unstructured":"MapReduce Tutorial. 2016. Retrieved from https:\/\/hadoop.apache.org\/docs\/r2.7.3\/hadoop-mapreduce-client\/hadoop-mapreduce-client-core\/MapReduceTutorial.html.  MapReduce Tutorial. 2016. Retrieved from https:\/\/hadoop.apache.org\/docs\/r2.7.3\/hadoop-mapreduce-client\/hadoop-mapreduce-client-core\/MapReduceTutorial.html."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2523616.2523633"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/PAAP.2014.29"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 21st IEEE International Conference on Network Protocols (ICNP\u201913)","author":"Xu Huanle","year":"2013","unstructured":"Huanle Xu and Wing Cheong Lau . 2013 . Resource optimization for speculative execution in a MapReduce Cluster . In Proceedings of the 21st IEEE International Conference on Network Protocols (ICNP\u201913) . 1--3. Huanle Xu and Wing Cheong Lau. 2013. Resource optimization for speculative execution in a MapReduce Cluster. In Proceedings of the 21st IEEE International Conference on Network Protocols (ICNP\u201913). 1--3."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/CLOUD.2014.84"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2015.42"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing (HotCloud\u201910)","author":"Zaharia Matei","year":"2010","unstructured":"Matei Zaharia , Mosharaf Chowdhury , Michael J. Franklin , Scott Shenker , and Ion Stoica . 2010 . Spark: Cluster computing with working sets . In Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing (HotCloud\u201910) . 10--10. Matei Zaharia, Mosharaf Chowdhury, Michael J. Franklin, Scott Shenker, and Ion Stoica. 2010. Spark: Cluster computing with working sets. In Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing (HotCloud\u201910). 10--10."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/1855741.1855744"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3225058.3225084"}],"container-title":["ACM Transactions on Modeling and Performance Evaluation of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3328740","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3328740","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:01Z","timestamp":1750204441000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3328740"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,12]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,9,30]]}},"alternative-id":["10.1145\/3328740"],"URL":"https:\/\/doi.org\/10.1145\/3328740","relation":{},"ISSN":["2376-3639","2376-3647"],"issn-type":[{"value":"2376-3639","type":"print"},{"value":"2376-3647","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,9,12]]},"assertion":[{"value":"2017-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-09-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}