Bit-sequences: A new cache invalidation method in mobile environments

In this paper, we address the problem of cache invalidation in mobile environments. We present Bit-Sequences, a new cache invalidation algorithm in which a periodically-broadcast invalidation report. is organi~cd as a set of binary bit sequences with an associated set of timestamps. A scal-able version of the Bit-Sequences algorithm for large databases, called Multi-Level Bit-Sequences, is also discussed. As demonstrated through simulation experiments, the Bit-Sequences algorithm performs consistently well under conditions of variable update rates/patterns and client discon-nection times. Furthermore, the size of the invalidation report in this algorithm is relatively small and is independent of the number of data items to be invalidated.