Space and write overhead are inversely proportional in flash memory

In this paper we consider the trade-off between space and write overhead of flash memory. Every flash memory has additional space to compensate for wear leveling; we denote the space overhead with σ. Furthermore, every flash memory is forced to rewrite valid data when a block is erased; we denote the write overhead with ω. We show that space and write overhead are inversely proportional with σω ≥ 1. We also present an algorithm that proves that our analysis is tight, as it achieves σω = 1 in a worst case. Moreover, we analyze a setting with the data being updated uniformly at random, or not at all.