Universal Rewriting in Constrained Memories

Jiang, Anxiao (Andrew) and Langberg, Michael and Schwartz, Moshe and Bruck, Jehoshua (2009) Universal Rewriting in Constrained Memories. Technical Report. California Institute of Technology, Pasadena, CA. [CaltechPARADISE:2009.ETR096]

Full text available as:

PDF - Requires Adobe Acrobat Reader or other PDF viewer.

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.

EPrint Type:	Monograph (Technical Report)
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.
Subjects:	All Records
ID Code:	127
Deposited By:	Caltech Library System
Deposited On:	21 September 2009
Record Number:	CaltechPARADISE:2009.ETR096
Official Persistent URL:	http://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.

Archive Staff Only: edit this record