Competitive On-Line Algorithms for Distributed Data Management
Carsten Lund, Nick Reingold, Jeffery Westbrook, Dicky Yan · SIAM Journal on Computing · 1998
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 networks---trees and bus-based networks---are studied. 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."