Approximate Counters for Flash Memory

Flash memory are very popular storage device. Due to its shock resistance and power economy it is adopted in sensor networks and embedded systems. Recently more attention is paid to the data storage in flash memory. Data in flash memory should be distributed evenly among data blocks. If the number of writes in a data block is too high, it may cause damage of the block. Requirements for highly reliable storage systems include efficient algorithms to maximize its lifetime and tools to predict it or monitor system status. One way to achieve this goal is to embed a system of counters which could control block usage (especially erasing operations). Some solutions of this kind including necessary algorithms are patented. In this paper we propose a solution involving the use of approximate counting of the number of block modifications. Our solution essentially reduces the number of bits needed to memorize counters and also essentially reduces the number of changes of counters. Our results are are based on new theoretical results about the behavior of a collection of probabilistic counters.