{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,27]],"date-time":"2025-11-27T10:34:23Z","timestamp":1764239663577,"version":"3.41.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2011,3,1]],"date-time":"2011-03-01T00:00:00Z","timestamp":1298937600000},"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. Algorithms"],"published-print":{"date-parts":[[2011,3]]},"abstract":"<jats:p>\n            Flash memories are widely used in computer systems ranging from embedded systems to workstations and servers to digital cameras and mobile phones. The memory cells of flash devices can only endure a limited number of write cycles, usually between 10,000 and 1,000,000. Furthermore, cells containing data must be\n            <jats:italic>erased<\/jats:italic>\n            before they can store new data, and erasure operations erase large blocks of memory, not individual cells. To maximize the endurance of the device (the amount of useful data that can be written to it before one of its cells wears out), flash-based systems move data around in an attempt to reduce the total number of erasures and to level the wear of the different erase blocks. This data movement introduces an interesting online problem called the\n            <jats:italic>wear-leveling problem<\/jats:italic>\n            . Wear-leveling algorithms have been used at least since 1993, but they have never been mathematically analyzed. In this article we analyze the two main wear-leveling problems. We show that a simple randomized algorithm for one of them is essentially optimal both in the competitive sense and in the absolute sense (our competitive result relies on an analysis of a nearly-optimal offline algorithm). We show that deterministic algorithms cannot achieve comparable endurance. We also analyze a more difficult problem and show that offline algorithms for it can improve upon naive approaches, but that online algorithms essentially cannot.\n          <\/jats:p>","DOI":"10.1145\/1921659.1921669","type":"journal-article","created":{"date-parts":[[2011,3,29]],"date-time":"2011-03-29T12:01:30Z","timestamp":1301400090000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Competitive analysis of flash memory algorithms"],"prefix":"10.1145","volume":"7","author":[{"given":"Avraham","family":"Ben-Aroya","sequence":"first","affiliation":[{"name":"Tel-Aviv University, Tel-Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sivan","family":"Toledo","sequence":"additional","affiliation":[{"name":"Tel-Aviv University, Tel-Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,3,31]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Assar M. Nemazie S. and Estakhri P. 1995. Flash memory mass storage architecture incorporation wear leveling technique. US patent 5479638.  Assar M. Nemazie S. and Estakhri P. 1995. Flash memory mass storage architecture incorporation wear leveling technique. US patent 5479638."},{"key":"e_1_2_1_2_1","unstructured":"Assar M. Nemazie S. and Estakhri P. 1996. Flash memory mass storage architecture incorporation wear leveling technique without using CAM cells. US patent 5485595.  Assar M. Nemazie S. and Estakhri P. 1996. Flash memory mass storage architecture incorporation wear leveling technique without using CAM cells. US patent 5485595."},{"key":"e_1_2_1_3_1","unstructured":"Ban A. 1995. Flash file system. US patent 5404485.  Ban A. 1995. Flash file system. US patent 5404485."},{"key":"e_1_2_1_4_1","unstructured":"Ban A. 1999. Flash file system optimized for page-mode flash technologies. US patent 5937425.  Ban A. 1999. Flash file system optimized for page-mode flash technologies. US patent 5937425."},{"key":"e_1_2_1_5_1","unstructured":"Ban A. 2004. Wear leveling of static areas in flash memory. US patent 6732221.  Ban A. 2004. Wear leveling of static areas in flash memory. US patent 6732221."},{"key":"e_1_2_1_6_1","unstructured":"Bruce R. H. Bruce R. H. Cohen E. T. and Christie A. J. 1999. Unified re-map and cache-index table with dual write-counters for wear-leveling of non-volitile flash ram mass storage. US patent 6000006.  Bruce R. H. Bruce R. H. Cohen E. T. and Christie A. J. 1999. Unified re-map and cache-index table with dual write-counters for wear-leveling of non-volitile flash ram mass storage. US patent 6000006."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0164-1212(99)00059-X"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-024X(199903)29:3%3C267::AID-SPE233%3E3.0.CO;2-T"},{"key":"e_1_2_1_9_1","unstructured":"Dan R. and Williams J. 1997. A TrueFFS and FLite technical overview of M-Systems' flash file systems. Tech. rep. 80-SR-002-00-6L Rev. 1.30 M-Systems-ch.  Dan R. and Williams J. 1997. A TrueFFS and FLite technical overview of M-Systems' flash file systems. Tech. rep. 80-SR-002-00-6L Rev. 1.30 M-Systems-ch."},{"key":"e_1_2_1_10_1","unstructured":"Estakhri P. Assar M. Reid R. Alan and Iman B. 1998. Method of and architecture for controlling system data with automatic wear leveling in a semiconductor non-volitile mass storage memory. US patent 5835935.  Estakhri P. Assar M. Reid R. Alan and Iman B. 1998. Method of and architecture for controlling system data with automatic wear leveling in a semiconductor non-volitile mass storage memory. US patent 5835935."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1089733.1089735"},{"key":"e_1_2_1_12_1","unstructured":"Han S.-W. 2000. Flash memory wear leveling system and method. US patent 6016275.  Han S.-W. 2000. Flash memory wear leveling system and method. US patent 6016275."},{"key":"e_1_2_1_13_1","volume-title":"J. H","author":"Jou E.","year":"1996","unstructured":"Jou , E. and Jeppesen III , J. H . 1996 . Flash memory wear leveling system providing immediate direct access to microprocessor. US patent 5568423. Jou, E. and Jeppesen III, J. H. 1996. Flash memory wear leveling system providing immediate direct access to microprocessor. US patent 5568423."},{"volume-title":"Proceedings of the USENIX Technical Conference. 155--164","author":"Kawaguchi A.","key":"e_1_2_1_14_1","unstructured":"Kawaguchi , A. , Nishioka , S. , and Motoda , H . 1995. A flash-memory based file system . In Proceedings of the USENIX Technical Conference. 155--164 . Kawaguchi, A., Nishioka, S., and Motoda, H. 1995. A flash-memory based file system. In Proceedings of the USENIX Technical Conference. 155--164."},{"key":"e_1_2_1_15_1","first-page":"950","article-title":"An effective flash memory manager for reliable flash memory space management. IEICE","volume":"6","author":"Kim H.-J.","year":"2002","unstructured":"Kim , H.-J. and Lee , S.-G. 2002 . An effective flash memory manager for reliable flash memory space management. IEICE Trans. Inf. Syst. E85-D , 6 , 950 -- 964 . Kim, H.-J. and Lee, S.-G. 2002. An effective flash memory manager for reliable flash memory space management. IEICE Trans. Inf. Syst. E85-D, 6, 950--964.","journal-title":"Trans. Inf. Syst. E85-D"},{"key":"e_1_2_1_16_1","unstructured":"Lofgren K. M. Norman R. D. Thelin Gregory B. and Gupta A. 2003. Wear leveling techniques for flash EEPROM systems. US patent 6594183.  Lofgren K. M. Norman R. D. Thelin Gregory B. and Gupta A. 2003. Wear leveling techniques for flash EEPROM systems. US patent 6594183."},{"key":"e_1_2_1_17_1","unstructured":"Lofgren K. M. J. Norman R. D. Thelin G. B. and Gupta A. 2000. Wear leveling techniques for flash EEPROM systems. US patent 6081447.  Lofgren K. M. J. Norman R. D. Thelin G. B. and Gupta A. 2000. Wear leveling techniques for flash EEPROM systems. US patent 6081447."},{"volume-title":"Probabilistic Methods for Algorithmic Discrete Mathematics","author":"McDiarmid C.","key":"e_1_2_1_18_1","unstructured":"McDiarmid , C. 1998. Concentration . In Probabilistic Methods for Algorithmic Discrete Mathematics , M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, and B. Reed Eds., Springer , 195--248. McDiarmid, C. 1998. Concentration. In Probabilistic Methods for Algorithmic Discrete Mathematics, M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, and B. Reed Eds., Springer, 195--248."},{"volume-title":"Proceedings of the 2nd International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM'98)","author":"Raab M.","key":"e_1_2_1_20_1","unstructured":"Raab , M. and Steger , A. 1998. \u201cBalls into bins\u201d\u2014A simple and tight analysis . In Proceedings of the 2nd International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM'98) . Springer, 159--170. Raab, M. and Steger, A. 1998. \u201cBalls into bins\u201d\u2014A simple and tight analysis. In Proceedings of the 2nd International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM'98). Springer, 159--170."},{"key":"e_1_2_1_21_1","unstructured":"Wells S. E. 1994. Method for wear leveling in a flash EEPROM memory. US patent 5341339.  Wells S. E. 1994. Method for wear leveling in a flash EEPROM memory. US patent 5341339."},{"key":"e_1_2_1_22_1","volume-title":"JFFS: The journaling flash file system","author":"Woodhouse D.","year":"2001","unstructured":"Woodhouse , D. 2001 . JFFS: The journaling flash file system . http:\/\/sources.redhat.com\/jffs2\/jffs2.pdf. Woodhouse, D. 2001. JFFS: The journaling flash file system. http:\/\/sources.redhat.com\/jffs2\/jffs2.pdf."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/195473.195506"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1921659.1921669","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1921659.1921669","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:08Z","timestamp":1750278368000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1921659.1921669"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,3]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,3]]}},"alternative-id":["10.1145\/1921659.1921669"],"URL":"https:\/\/doi.org\/10.1145\/1921659.1921669","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2011,3]]},"assertion":[{"value":"2007-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-03-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}