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 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 [9] and "factoring." Key words. on-line algorithms, competitive analysis, memory management, data management. AMS subject classifications. 68Q20, 68Q25. 1. Introduction. The management of data in a distributed network is an important and much studied problem in management science, engineering, computer systems and theory [3, 11]. Dowdy and Foster [11] give a comprehensive survey of research in th..