migration with limited local memory capacity

Abstract. Most previous work on page migration assumes that each pro-cessor, in the given distributed environment, has innite local memory capacity. In this paper we study the migration problem under the realistic assumption that the local memories have limited capacities. We assume that the memories are direct-mapped, i.e., the processors use a hash func-tion in order to locate pages in their memory. We show that, for a number of important network topologies, on-line algorithms with a constant com-petitive ratio can be developed in this model. We also study distributed paging. We examine the migration version of this problem in which there exists only one copy of each page. We develop ecient deterministic and randomized on-line algorithms for this problem.