Bit-Sequences: A Cache Invalidation Algorithm in Mobile Environments
Jing Jin, Omran Bukhres, Ahmed K. Elmagarmid, Rafael del Hoyo Alonso · Purdue e-Pubs (Purdue University System) · 1994
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 organized as a set of binary bit sequences with an associated set of timestamps.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.Scalable versions of the Bit-Sequences algorithm are also discussed.