Competitive on-line algorithms for distributed data management

Competitive on-line algorithms for data management in a network of processo rs are studied in this paper. A data object such as a file or a page of vir tual 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 sequ ence 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 techni ques, such as work functions [Chrobak and Larmore, Proc. DIMACS Workshop on On-Line Algorithms, AMS, 1991, pp. 11-64] and "factoring."