{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:42:45Z","timestamp":1750308165703,"version":"3.41.0"},"reference-count":16,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2005,5,1]],"date-time":"2005-05-01T00:00:00Z","timestamp":1114905600000},"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. Storage"],"published-print":{"date-parts":[[2005,5]]},"abstract":"<jats:p>A file storage scheme is proposed for networks containing heterogeneous clients. In the scheme, the performance measured by file-retrieval delays degrades gracefully under increasingly serious faulty circumstances. The scheme combines coding with storage for better performance. The problem is NP-hard for general networks; and this article focuses on tree networks with asymmetric edges between adjacent nodes. A polynomial-time memory-allocation algorithm is presented, which determines how much data to store on each node, with the objective of minimizing the total amount of data stored in the network. Then a polynomial-time data-interleaving algorithm is used to determine which data to store on each node for satisfying the quality-of-service requirements in the scheme. By combining the memory-allocation algorithm with the data-interleaving algorithm, an optimal solution to realize the file storage scheme in tree networks is established.<\/jats:p>","DOI":"10.1145\/1063786.1063788","type":"journal-article","created":{"date-parts":[[2005,8,1]],"date-time":"2005-08-01T15:52:42Z","timestamp":1122911562000},"page":"171-189","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Network file storage with graceful performance degradation"],"prefix":"10.1145","volume":"1","author":[{"given":"Anxiao (Andrew)","family":"Jiang","sequence":"first","affiliation":[{"name":"California Institute of Technology, Pasadena, CA"}]},{"given":"Jehoshua","family":"Bruck","sequence":"additional","affiliation":[{"name":"California Institute of Technology, Pasadena, CA"}]}],"member":"320","published-online":{"date-parts":[[2005,5]]},"reference":[{"volume-title":"Online Computation and Competitive Analysis","author":"Borodin A.","key":"e_1_2_1_1_1","unstructured":"Borodin , A. and El-Yaniv , R. 1998. Online Computation and Competitive Analysis . Cambridge University Press , Cambridge, U.K. Borodin, A. and El-Yaniv, R. 1998. Online Computation and Competitive Analysis. Cambridge University Press, Cambridge, U.K."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/356876.356883"},{"key":"e_1_2_1_3_1","unstructured":"Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company New York NY and San Francisco CA.   Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company New York NY and San Francisco CA."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.10.2.180"},{"key":"e_1_2_1_5_1","unstructured":"Jiang A. and Bruck J. 2003a. Diversity coloring for distributed data storage in networks. Unpublished manuscript.  Jiang A. and Bruck J. 2003a. Diversity coloring for distributed data storage in networks. Unpublished manuscript."},{"volume-title":"Proceedings of the IEEE International Symposium on Information Theory","author":"Jiang A.","key":"e_1_2_1_6_1","unstructured":"Jiang , A. and Bruck , J . 2003b. Memory allocation in information storage networks . In Proceedings of the IEEE International Symposium on Information Theory , ( Tokohama, Japan). 453. Jiang, A. and Bruck, J. 2003b. Memory allocation in information storage networks. In Proceedings of the IEEE International Symposium on Information Theory, (Tokohama, Japan). 453."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2004.840893"},{"volume-title":"Proceedings of the IEEE International Symposium on Information Theory","author":"Jiang A.","key":"e_1_2_1_8_1","unstructured":"Jiang , A. , Cook , M. , and Bruck , J . 2004. Optimal t-interleaving on tori . In Proceedings of the IEEE International Symposium on Information Theory ( Chicago, IL). 22. Jiang, A., Cook, M., and Bruck, J. 2004. Optimal t-interleaving on tori. In Proceedings of the IEEE International Symposium on Information Theory (Chicago, IL). 22."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.932716"},{"key":"e_1_2_1_10_1","first-page":"3","article-title":"An algorithmic approach to network location problems. I: The p-centers","volume":"37","author":"Kariv O.","year":"1979","unstructured":"Kariv , O. and Hakimi , S. L. 1979 . An algorithmic approach to network location problems. I: The p-centers . SIAM J. Appl. Math. 37 , 3 (Dec.), 513--538. Kariv, O. and Hakimi, S. L. 1979. An algorithmic approach to network location problems. I: The p-centers. SIAM J. Appl. Math. 37, 3 (Dec.), 513--538.","journal-title":"SIAM J. Appl. Math."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/320434.320449"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.737699"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792237462"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/50202.50214"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/321958.321964"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/505696.505701"}],"container-title":["ACM Transactions on Storage"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1063786.1063788","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1063786.1063788","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:19:11Z","timestamp":1750263551000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1063786.1063788"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,5]]},"references-count":16,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2005,5]]}},"alternative-id":["10.1145\/1063786.1063788"],"URL":"https:\/\/doi.org\/10.1145\/1063786.1063788","relation":{},"ISSN":["1553-3077","1553-3093"],"issn-type":[{"type":"print","value":"1553-3077"},{"type":"electronic","value":"1553-3093"}],"subject":[],"published":{"date-parts":[[2005,5]]},"assertion":[{"value":"2005-05-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}