Bit-Sequences: A New Cache Invalidation Method in Mobile Environments
Jing Jin, Ahmed K. Elmagarmid, Sumi Helal, Rafael del Hoyo Alonso · Purdue e-Pubs (Purdue University System) · 1995
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 scalable 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 disconnection 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.