Mobile Data Access, Cache Invalidation, Disconnected Operation, Data Broadcast
Abstract
Abstract—In this paper, we address the problem of cache invalidation in mobile and wireless client/server environments. We present cache invalidation techniques that can scale not only to a large number of mobile clients, but also to a large number of data items that can be cached in the mobile clients. We propose two scalable algorithms: the Multidimensional Bit-Sequence (MD-BS) algorithm and the Multilevel Bit-Sequence (ML-BS) algorithm. Both algorithms are based on our prior work on the Basic Bit-Sequences (BS) algorithm. Our study shows that the proposed algorithms are effective for a large number of cached data items with low update rates. The study also illustrates that the algorithms can be used with other complementary techniques to address the problem of cache invalidation for data items with varied update and access rates.
1. S. Acharya, R. Alonso, M. Franklin, and S. Zdonik, "Broadcast Disks: Data Management for Asymmetric Communications Environments," Proc. ACM SIGMOD Conf. Management of Data, 1995.
2. D. Barbara, and T. Imielinski, "Sleepers and Workaholics: Caching Strategies for Mobile Environments," Proc. ACM SIGMOD Conf. Management of Data, pp. 1-12, 1994.
3. M.J. Franklin, "Caching and Memory Management in Client-Server Database Systems," PhD thesis, Univ. of Wisconsin-Madison, 1993.
4. Y. Huang, P. Sistla, and O. Wolfson, "Data Replication for Mobile Computers," Proc. ACM SIGMOD Conf. Management of Data, 1994.
5. T. Imielinski, and B.R. Badrinath, "Wireless Mobile Computing: Challenges in Data Management," Comm. ACM, vol. 37, no. 10, 1994.
6. T. Imielinski, S. Vishwanath, and B.R. Badrinath, "Energy Efficient Indexing on Air," Proc. ACM SIGMOD Conf. Management of Data, 1994.
7. J. Jing, A. Elmagarmid, A. Helal, and R. Alonso, "Bit-Sequences: An Adaptive Cache Invalidation Method in Mobile Client/Server Environments," ACM/Baltzer J. Mobile Networks and Applications, vol. 2, no. 2, pp. 115-127, Oct. 1997.
8. V. Liberatore, "Multicast Scheduling for List Requests," Proc. INFOCOM, pp. 1129-1137, 2002.
9. L.B. Mummert, and M. Satyanarayanan, "Variable Granularity Cache Coherence," Operating Systems Rev., vol. 28, no. 1, Jan. 1994.
10. K.-L. Tan, J. Cai, and B.C. Ooi, "An Evaluation of Cache Invalidation Strategies in Wireless Environments," IEEE Trans. Parallel and Distributed Systems, vol. 12, no. 8, pp. 789-807, Aug. 2001.
11. K. Wu, P. Yu, and M. Chen, "Energy-Efficient Caching for Wireless Mobile Computing," Proc. IEEE Data Eng. Conf., 1996.
