DISTRIBUTED PAGING FOR GENERAL NETWORKS

Distributed paging deals with the dynamic allocation of copies of file s in a distributed network as to minimize the total communication cost over a sequence of read and write requests. Most previous work deals with the file allocation problem, where infinite nodal memory capacity is assumed. In contrast the distributed paging problem makes the more realistic assumption that nodal memory capacity is limited. Former wo rk on distributed paging deals with the problem only in the case of a uniform network topology. This paper gives the first distributed pagin g algorithm for general networks. The algorithm is competitive in stor age and communication. The competitive rates are poly-logarithmic in t he total number of network nodes and the diameter of the network. (C) 1998 Academic Press.