MPI-I-94-106
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: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1994-106
BibTeX
@TECHREPORT{AlbersKoga94,
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},
}