A strongly consistent cached data access algorithm for wireless data networks

In wireless data networks such as the WAP system, the cached data may be time-sensitive and thus strong consistency must be maintained, i.e., the data presented to the user at the WAP handset must be the same as that in the origin server. In this paper, a strongly consistent cached data access algorithm, Probability-Based Callback (pCB in short), is proposed for such networks. In the pCB, upon an update arrival, the action taken by the server is not deterministic; the server can either invalidate the cached data entry in the client or send the updated data entry to the client. The pCB scheme can make good tradeoff between communication cost and access delay, which is extremely difficult for most of the existing cache access schemes. Besides, the pCB scheme possesses excellent universal adaptability and thus can adapt to the inherent heterogeneity of wireless networks and applications. We analytically model the pCB scheme, and derive closed-form analytical formulae for the mean communication cost per data entry access and the mean access delay under a general assumption on distributions of the inter-update and inter-access times. It is demonstrated that the existing Push and Callback schemes are special cases of the pCB scheme.