Page migration with limited local memory capacity
Susanne Albers, Hisashi Koga · 1995
. Most previous work on page migration assumes that each processor, in the given distributed environment, has infinite 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 function in order to locate pages in their memory. We show that, for a number of important network topologies, on-line algorithms with a constant competitive 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 efficient deterministic and randomized on-line algorithms for this problem. 1 Introduction Many on-line problems of practical significance arise in distributed data management. As a result, there has recently been a lot of research interests in problems such as page migration, page replication and distributed pa...