{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,8]],"date-time":"2026-02-08T19:07:51Z","timestamp":1770577671791,"version":"3.49.0"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2020,5,22]],"date-time":"2020-05-22T00:00:00Z","timestamp":1590105600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ISF","award":["1030\/15"],"award-info":[{"award-number":["1030\/15"]}]},{"name":"NSF","award":["CCF1618603 and CCF1814487"],"award-info":[{"award-number":["CCF1618603 and CCF1814487"]}]},{"name":"NSF-BSF","award":["2015814"],"award-info":[{"award-number":["2015814"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Storage"],"published-print":{"date-parts":[[2020,5,31]]},"abstract":"<jats:p>Erasure codes in large-scale storage systems allow recovery of data from a failed node. A recently developed class of codes, locally repairable codes (LRCs), offers tradeoffs between storage overhead and repair cost. LRCs facilitate efficient recovery scenarios by adding parity blocks to the system. However, these additional blocks may eventually increase the number of blocks that must be reconstructed. Existing LRCs differ in their use of the parity blocks, in their locality semantics, and in their parameter space. Thus, existing theoretical models cannot directly compare different LRCs to determine which code offers the best recovery performance, and at what cost.<\/jats:p>\n          <jats:p>We perform the first systematic comparison of existing LRC approaches. We analyze Xorbas, Azure\u2019s LRCs, and Optimal-LRCs in light of two new metrics: average degraded read cost and normalized repair cost. We show the tradeoff between these costs and the code\u2019s fault tolerance, and that different approaches offer different choices in this tradeoff. Our experimental evaluation on a Ceph cluster further demonstrates the different effects of realistic system bottlenecks on the benefit from each LRC approach. Despite these differences, the normalized repair cost metric can reliably identify the LRC approach that would achieve the lowest repair cost in each setup.<\/jats:p>","DOI":"10.1145\/3381832","type":"journal-article","created":{"date-parts":[[2020,5,25]],"date-time":"2020-05-25T22:07:11Z","timestamp":1590444431000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":25,"title":["On Fault Tolerance, Locality, and Optimality in Locally Repairable Codes"],"prefix":"10.1145","volume":"16","author":[{"given":"Oleg","family":"Kolosov","sequence":"first","affiliation":[{"name":"Tel Aviv University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gala","family":"Yadgar","sequence":"additional","affiliation":[{"name":"Technion, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matan","family":"Liram","sequence":"additional","affiliation":[{"name":"Technion, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Itzhak","family":"Tamo","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Barg","sequence":"additional","affiliation":[{"name":"University of Maryland, Moscow, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,5,22]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Retrieved","year":"2017"},{"key":"e_1_2_1_2_1","volume-title":"Retrieved","year":"2017"},{"key":"e_1_2_1_3_1","volume-title":"Retrieved","year":"2017"},{"key":"e_1_2_1_4_1","volume-title":"Retrieved","author":"Hadoop Apache","year":"2017"},{"key":"e_1_2_1_5_1","volume-title":"Retrieved","year":"2017"},{"key":"e_1_2_1_6_1","volume-title":"Retrieved","year":"2017"},{"key":"e_1_2_1_7_1","volume-title":"Retrieved","year":"2018"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 21st Annual International Symposium on Computer Architecture (ISCA\u201994)","author":"Blaum M."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 2017 USENIX Annual Technical Conference (ATC\u201917)","author":"Chen Yu Lin","year":"2017"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2010.2054295"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSN.2018.00030"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2013.6620354"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2012.2208937"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897525"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2435204.2435207","article-title":"Pyramid codes: Flexible schemes to trade space for access efficiency in reliable data storage systems","volume":"9","author":"Huang Cheng","year":"2013","journal-title":"ACM Transactions on Storage"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the USENIX Annual Technical Conference (ATC\u201912)","author":"Huang Cheng","year":"2012"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 17th USENIX Conference on File and Storage Technologies (FAST\u201919)","author":"Kadekodi Saurabh"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 10th USENIX Conference on File and Storage Technologies (FAST\u201912)","author":"Khan Osama","year":"2012"},{"key":"e_1_2_1_19_1","volume-title":"On Fault Tolerance, Locality, and Optimality in Locally Repairable Codes. Master\u2019s Thesis. School of Electrical Engineering","author":"Kolosov Oleg","year":"2041"},{"key":"e_1_2_1_20_1","unstructured":"Oleg Kolosov Alexander Barg Itzhak Tamo and Gala Yadgar. 2018. Optimal LRC codes for all lengths n <= q. arXiv:1802.00157.  Oleg Kolosov Alexander Barg Itzhak Tamo and Gala Yadgar. 2018. Optimal LRC codes for all lengths n <= q . arXiv:1802.00157."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 2018 USENIX Annual Technical Conference (USENIX ATC\u201918)","author":"Kolosov Oleg","year":"2018"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/378993.379239"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2016.2590429"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2658991"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 2017 USENIX Annual Technical Conference (ATC\u201917)","author":"Li Runhui","year":"2017"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 17th USENIX Conference on File and Storage Technologies (FAST\u201919)","author":"Li Xiaolu","year":"2019"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2017.2713245"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2901318.2901328"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201912)","author":"Nightingale Edmund B.","year":"2012"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2011.5934901"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 14th USENIX Conference on File and Storage Technologies (FAST\u201916)","author":"Pamies-Juarez Lluis","year":"2016"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2560013"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 11th USENIX Conference on File and Storage Technologies (FAST\u201913)","author":"Plank James S."},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 7th USENIX Conference on File and Storage Technologies (FAST\u201909)","volume":"9","author":"Plank James S.","year":"2009"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 13th USENIX Conference on File and Storage Technologies (FAST\u201915)","author":"Rashmi K. V.","year":"2015"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the 5th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage\u201913)","author":"Rashmi K. V.","year":"2013"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2740070.2626325"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2011.2159049"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/0108018"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the 7th Annual Workshop on the Interaction Amongst Virtualization, Operating Systems, and Computer Architecture (WIVOSCA\u201913)","author":"Rosenfeld Eitan","year":"2013"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535573.2488339"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2016.2591040"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3211890.3211896"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611354.2611370"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2321280"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2012.2227110"},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of the 16th USENIX Conference on File and Storage Technologies (FAST\u201918)","author":"Vajha Myna"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2538542.2538562"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/GLOCOMW.2010.5700274"},{"key":"e_1_2_1_50_1","volume-title":"Proceedings of the 2019 USENIX Annual Technical Conference (USENIX ATC\u201919)","author":"Wang Zhufan","year":"2019"},{"key":"e_1_2_1_51_1","volume-title":"Proceedings of the 7th Symposium on Operating Systems Design and Implementation (OSDI\u201906)","author":"Weil Sage A.","year":"2006"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2006.19"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374596.1374606"},{"key":"e_1_2_1_54_1","volume-title":"Proceedings of the 13th USENIX Conference on File and Storage Technologies (FAST\u201915)","author":"Xia Mingyuan"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSST.2019.00004"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2017.2661313"},{"key":"e_1_2_1_57_1","unstructured":"Alexander Zeh and Eitan Yaakobi. 2016. Bounds and constructions of codes with multiple localities. arXiv:1601.02763.  Alexander Zeh and Eitan Yaakobi. 2016. Bounds and constructions of codes with multiple localities. arXiv:1601.02763."},{"key":"e_1_2_1_58_1","volume-title":"Proceedings of the 16th USENIX Conference on File and Storage Technologies (FAST\u201918)","author":"Zhang Guangyan","year":"2018"},{"key":"e_1_2_1_59_1","volume-title":"Proceedings of the 17th USENIX Conference on File and Storage Technologies (FAST\u201919)","author":"Zhou Tianli","year":"2019"}],"container-title":["ACM Transactions on Storage"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3381832","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3381832","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:33:07Z","timestamp":1750199587000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3381832"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,22]]},"references-count":59,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,5,31]]}},"alternative-id":["10.1145\/3381832"],"URL":"https:\/\/doi.org\/10.1145\/3381832","relation":{},"ISSN":["1553-3077","1553-3093"],"issn-type":[{"value":"1553-3077","type":"print"},{"value":"1553-3093","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,5,22]]},"assertion":[{"value":"2019-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-05-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}