We present improved competitive on-line algorithms for the
page replication problem and concentrate on important network topolo-
gies for which algorithms with a constant competitive factor can be given.
We develop an optimal randomized on-line replication algorithm for trees
and uniform networks; its competitive factor is approximately 1.58. Fur-
thermore we consider on-line replication algorithms for rings and present
general techniques that transform large classes of c-competitive algo-
rithms 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.