MPI-INF/SWS Research Reports 1991-2021

2. Number - All Departments


New on-line algorithms for the page replication problem

Albers, Susanne and Koga, Joachim

February 1994, 18 pages.

Status: available - back from printing

The page replication problem arises in the memory management of large multiprocessor systems. Given a network of processors, each of which has its local memory, the problem consists of deciding which local memories should contain copies of pages of data so that a sequence of memory accesses can be accomplished efficiently. We present new competitive on-line algorithms for the page replication problem and concentrate on important network topologies for which algorithms with a constant competitive factor can be given. We develop the first optimal randomized on-line replication algorithm for trees and uniform networks; its competitive factor is approximately 1.58. Furthermore we consider on-line replication algorithms for rings and present general techniques that transform large classes of $c$-competitive algorithms for trees into $2c$-competitive algorithms for rings. As a result we obtain a randomized on-line algorithm for rings that is 3.16-competitive. We also derive two 4-competitive on-line algorithms for rings which are either deterministic or memoryless. All our algorithms improve the previously best competitive factors for the respective topologies.

URL to this document:

Hide details for BibTeXBibTeX
  AUTHOR = {Albers, Susanne and Koga, Joachim},
  TITLE = {New on-line algorithms for the page replication problem},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-94-106},
  MONTH = {February},
  YEAR = {1994},
  ISSN = {0946-011X},