{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:29:49Z","timestamp":1750220989609,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,3,3]],"date-time":"2019-03-03T00:00:00Z","timestamp":1551571200000},"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":["ACM Trans. Model. Perform. Eval. Comput. Syst."],"published-print":{"date-parts":[[2019,3,31]]},"abstract":"<jats:p>\n            Matrix analytic methods are developed to compute the probability distribution of response times (i.e., data access times) in distributed storage systems protected by erasure coding, which is implemented by sharding a data object into\n            <jats:italic>N<\/jats:italic>\n            fragments, only\n            <jats:italic>K<\/jats:italic>\n            &lt;;\n            <jats:italic>N<\/jats:italic>\n            of which are required to reconstruct the object. This leads to a partial-fork-join model with a choice of canceling policies for the redundant\n            <jats:italic>N<\/jats:italic>\n            \u2212\n            <jats:italic>K<\/jats:italic>\n            tasks. The accuracy of the analytical model is supported by tests against simulation in a broad range of setups. At increasing workload intensities, numerical results show the extent to which increasing the redundancy level reduces the mean response time of storage reads and significantly flattens the tail of their distribution; this is demonstrated at medium-high quantiles, up to the 99th. The quantitative reduction in response time achieved by two policies for canceling redundant tasks is also shown: for cancel-at-finish and cancel-at-start, which limits the additional load introduced whilst losing the benefit of selectivity amongst fragment service times.\n          <\/jats:p>","DOI":"10.1145\/3300143","type":"journal-article","created":{"date-parts":[[2019,3,4]],"date-time":"2019-03-04T13:31:47Z","timestamp":1551706307000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Managing Response Time Tails by Sharding"],"prefix":"10.1145","volume":"4","author":[{"given":"P. G.","family":"Harrison","sequence":"first","affiliation":[{"name":"Imperial College London, London, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"N. M.","family":"Patel","sequence":"additional","affiliation":[{"name":"NetApp Inc, Sunnyvale, California"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. F.","family":"P\u00e9rez","sequence":"additional","affiliation":[{"name":"Universidad del Rosario, Colombia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Z.","family":"Qiu","sequence":"additional","affiliation":[{"name":"Imperial College London, London, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,3,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/2342763.2342780"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1011083915877"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"D. A. Bini B. Iannazzo and B. Meini. 2012. Numerical Solution of Algebraic Riccati Equations SIAM Book Series Fundamentals of Algorithms. SIAM.   D. A. Bini B. Iannazzo and B. Meini. 2012. Numerical Solution of Algebraic Riccati Equations SIAM Book Series Fundamentals of Algorithms. SIAM.","DOI":"10.1137\/1.9781611972092"},{"volume-title":"Proceedings of the IEEE Conference on Computer Communications (INFOCOM\u201914)","author":"Chen Shengbo","key":"e_1_2_1_4_1","unstructured":"Shengbo Chen , Yin Sun , Ulas C. Kozat , Longbo Huang , Pradeep Sinha , Guanfeng Liang , Xin Liu , and Ness B. Shroff . 2014. When queueing meets coding: Optimal-latency data retrieving scheme in storage clouds . In Proceedings of the IEEE Conference on Computer Communications (INFOCOM\u201914) . 1042--1050. Shengbo Chen, Yin Sun, Ulas C. Kozat, Longbo Huang, Pradeep Sinha, Guanfeng Liang, Xin Liu, and Ness B. Shroff. 2014. When queueing meets coding: Optimal-latency data retrieving scheme in storage clouds. In Proceedings of the IEEE Conference on Computer Communications (INFOCOM\u201914). 1042--1050."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2408776.2408794"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/MASCOTS.2016.43"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/11777830_8"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2012.6284026"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2014.140518"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ALLERTON.2015.7446992"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055281"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/509058.509086"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the International Conference on Communications","volume":"2","author":"Kleinrock Leonard","year":"1978","unstructured":"Leonard Kleinrock . 1978 . On flow control in computer networks . In Proceedings of the International Conference on Communications , Vol. 2 . 27--2. Leonard Kleinrock. 1978. On flow control in computer networks. In Proceedings of the International Conference on Communications, Vol. 2. 27--2."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2901318.2901337"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-5316(99)00061-9"},{"volume-title":"Introduction to Parallel Computing: Design and Analysis of Algorithms","author":"Kumar Vipin","key":"e_1_2_1_17_1","unstructured":"Vipin Kumar , Ananth Grama , Anshul Gupta , and George Karypis . 1994. Introduction to Parallel Computing: Design and Analysis of Algorithms . Benjamin-Cummings Publishing Co., Inc. , Redwood City, CA . Vipin Kumar, Ananth Grama, Anshul Gupta, and George Karypis. 1994. Introduction to Parallel Computing: Design and Analysis of Algorithms. Benjamin-Cummings Publishing Co., Inc., Redwood City, CA."},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Guy Latouche and Vaidyanathan Ramaswami. 1999. Introduction to Matrix Analytic Methods in Stochastic Modeling. SIAM.  Guy Latouche and Vaidyanathan Ramaswami. 1999. Introduction to Matrix Analytic Methods in Stochastic Modeling. SIAM.","DOI":"10.1137\/1.9780898719734"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.1979.1102178"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2017.2674671"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3159172"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2013.2289382"},{"key":"e_1_2_1_23_1","unstructured":"F. J. MacWilliams and N. J. A. Sloane. 1977. The Theory of Error Correcting Codes. North Holland.  F. J. MacWilliams and N. J. A. Sloane. 1977. The Theory of Error Correcting Codes. North Holland."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2825236.2825248"},{"key":"e_1_2_1_26_1","first-page":"1","article-title":"Cutting latency tail: Analyzing and validating replication without canceling","volume":"99","author":"Qiu Z.","year":"2017","unstructured":"Z. Qiu , J. F. Perez Bernal , R. Birke , L. Chen , and P. G. Harrison . 2017 . Cutting latency tail: Analyzing and validating replication without canceling . IEEE Trans. Parallel Distrib. Syst. 99 (2017), 1 -- 1 . Z. Qiu, J. F. Perez Bernal, R. Birke, L. Chen, and P. G. Harrison. 2017. Cutting latency tail: Analyzing and validating replication without canceling. IEEE Trans. Parallel Distrib. Syst. 99 (2017), 1--1.","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2015.06.007"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2017.2706268"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.2307\/1427202"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOMM.2015.2506161"},{"volume-title":"Proceedings of the IEEE Conference on Computer Communications (INFOCOM\u201915)","author":"Sun Y.","key":"e_1_2_1_32_1","unstructured":"Y. Sun , Z. Zheng , C. E. Koksal , K. Kim , and N. B. Shroff . 2015. Provably delay efficient data retrieving in storage clouds . In Proceedings of the IEEE Conference on Computer Communications (INFOCOM\u201915) . 585--593. Y. Sun, Z. Zheng, C. E. Koksal, K. Kim, and N. B. Shroff. 2015. Provably delay efficient data retrieving in storage clouds. In Proceedings of the IEEE Conference on Computer Communications (INFOCOM\u201915). 585--593."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2007.11.002"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1100.0387"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2667522.2667524"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2015.2466453"}],"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\/3300143","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3300143","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:25:22Z","timestamp":1750206322000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3300143"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,3]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,3,31]]}},"alternative-id":["10.1145\/3300143"],"URL":"https:\/\/doi.org\/10.1145\/3300143","relation":{},"ISSN":["2376-3639","2376-3647"],"issn-type":[{"type":"print","value":"2376-3639"},{"type":"electronic","value":"2376-3647"}],"subject":[],"published":{"date-parts":[[2019,3,3]]},"assertion":[{"value":"2017-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-03-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}