TY - GEN
T1 - Page migration with limited local memory capacity
AU - Albers, Susanne
AU - Koga, Hisashi
N1 - Publisher Copyright:
© 1995, Springer-Verlag. All rights reserved.
PY - 1995
Y1 - 1995
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/84958062172
U2 - 10.1007/3-540-60220-8_58
DO - 10.1007/3-540-60220-8_58
M3 - Conference contribution
AN - SCOPUS:84958062172
SN - 3540602208
SN - 9783540602200
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 147
EP - 158
BT - Algorithms and Data Structures - 4th International Workshop, WADS 1995, Proceedings
A2 - Akl, Selim G.
A2 - Dehne, Frank
A2 - Sack, Jörg-Rüdiger
A2 - Santoro, Nicola
PB - Springer Verlag
T2 - 4th Workshop on Algorithms and Data Structures, WADS 1995
Y2 - 16 August 1995 through 18 August 1995
ER -