Jiang, Anxiao (Andrew) and Langberg, Michael and Schwartz, Moshe and Bruck, Jehoshua (2009) Universal Rewriting in Constrained Memories. California Institute of Technology , Pasadena, CA. (Unpublished) https://resolver.caltech.edu/CaltechPARADISE:2009.ETR096
![]()
|
PDF
See Usage Policy. 155kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechPARADISE:2009.ETR096
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.
Item Type: | Report or Paper (Technical Report) | ||||||||
---|---|---|---|---|---|---|---|---|---|
ORCID: |
| ||||||||
Additional Information: | 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. | ||||||||
Group: | Parallel and Distributed Systems Group | ||||||||
Record Number: | CaltechPARADISE:2009.ETR096 | ||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechPARADISE:2009.ETR096 | ||||||||
Official Citation: | Anxiao (Andrew) Jiang, Michael Langberg, Moshe Schwartz, and Jehoshua Bruck. Universal Rewriting in Constrained Memories. Technical Report. California Institute of Technology, Pasadena, CA. [CaltechPARADISE:2009.ETR096] | ||||||||
Usage Policy: | You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format. | ||||||||
ID Code: | 26127 | ||||||||
Collection: | CaltechPARADISE | ||||||||
Deposited By: | Imported from CaltechPARADISE | ||||||||
Deposited On: | 21 Sep 2009 | ||||||||
Last Modified: | 18 Aug 2021 01:36 |
Repository Staff Only: item control page