Divergence Caching in Client-Server Architectures

In this paper we propose a new mechanism, divergence caching, for reducing access and communication charges in accessing on-line database servers. The objective is achieved by allowing tolerant read requests, namely requests that can be satisfied by out-of-date data. We propose two algorithms based on divergence caching, Static and Dynamic. The first is appropriate when the access pattern to an object in the database is fixed and known, and the latter is appropriate in other cases. We analyze these algorithms in the worst case and the expected case. 1 Introduction and overview Users will soon have on-line access to a large number of databases, often via wireless networks. The potential market for this activity is estimated to be billions of dollars annually, in access and communication charges. For example, passengers will access airline and other carriers' schedules, and weather information. Investors will access prices of financial instruments, salespeople will access inventory data..