Competitive on-line algorithms for distributed data management

Competitive on-line algorithms for data management in a network of processors are studied in this paper. A data object such as a file or a page of virtual memory is to be read and updated by various processors in the network. The goal is to minimize the communication costs incurred in serving a sequence of such requests. Distributed data management on important classes of networksd. Optimal algorithms with constant competitive ratios and matching lower bounds are obtained. Our algorithms use different interesting techniques, such as work functions {[}Chrobak and Larmore, Proc. DIMACS Workshop on On-Line Algorithms, AMS, 1991, pp. 11-64] and ``factoring.{''}