Competitive Algorithms for Asynchronous Update Propogation in Mobile Computing and for Search Engine Freshness
Vijay Gupta, Roy Campbell · 2000
Mobile computing has become a hot area of research because of proliferation of laptop computers. Some of the challenges in using wireless networks for mobile computing are low bandwidth and high communication cost. To address these challenges, researchers have built systems in which the file system contents on the backbone file server are optimistically replicated on the laptop. The problem of how often to send the updates from the laptop to the backbone server for optimistically replicated filesystems remains unsolved. Search engine freshness has become an important problems with the emergence of search engines which cache a copy of the document. Such a cache can provide valuable fault tolerance when the original web site is unreachable. Because of the growing use of laptops and search engines, maintaining freshness of data is becoming an important problem. There is very sparse literature on solving the problem of freshness. In this paper, we introduce a cost model which takes into account the utility of freshness, and use that model to develop 2-competitive algorithms for asynchronous update propagation. Our model is flexible so that it is possible to adapt it to preserve causality and competitiveness for mobile computing. Although at first sight, consistency for mobile computing and web might look different, our cost model is suitable for timely propagation of updates to web documents as well.