Universal rewriting in constrained memories
Abstract
A constrained memory is a storage device whose elements change their states under some constraints. A typical example is flash memories, in which cell levels are easy to increase but hard to decrease. In a general rewriting model, the stored data changes with some pattern determined by the application. In a constrained memory, an appropriate representation is needed for the stored data to enable efficient rewriting. In this paper, we define the general rewriting problem using a graph model. This model generalizes many known rewriting models such as floating codes, WOM codes, buffer codes, etc. We present a novel rewriting scheme for the flash-memory model and prove it is asymptotically optimal in a wide range of scenarios. We further study randomization and probability distributions to data rewriting and study the expected performance. We present a randomized code for all rewriting sequences and a deterministic code for rewriting following any i.i.d, distribution. Both codes are shown to be optimal asymptotically.
Additional Information
© 2009 IEEE. This work was supported in part by the NSF CAREER Award CCF-0747415, the NSF grant ECCS-0802107, the ISF grant 480/08, the GIF grant 2179-1785.10/2007, and the Caltech Lee Center for Advanced Networking.Attached Files
Published - 05205981.pdf
Files
Name | Size | Download all |
---|---|---|
md5:1c96d4d58ca17ee9937aedae44a633a6
|
966.7 kB | Preview Download |
Additional details
- Eprint ID
- 75294
- Resolver ID
- CaltechAUTHORS:20170321-172544029
- CCF-0747415
- NSF
- ECCS-0802107
- NSF
- 480/08
- Israel Science Foundation
- 2179-1785.10/2007
- German-Israeli Foundation for Research and Development
- Caltech Lee Center for Advanced Networking
- Created
-
2017-03-22Created from EPrint's datestamp field
- Updated
-
2021-11-15Created from EPrint's last_modified field