New On-Line Algorithms for the Page Replication Problem

We present improved competitive on-line algorithms for the page replication problem and concentrate on important network topologies for which algorithms with a constant competitive ratio can be given. We develop an optimal randomized on-line replication algorithm for trees and uniform networks; its competitive ratio is approximately 1.58. This performance holds against oblivious adversaries. We also give a randomized memoryless replication algorithm for trees and uniform networks that is 2-competitive against adaptive on-line adversaries. Furthermore, we consider on-line replication algorithms for rings and present general techniques that transform 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 randomized and memoryless. Again, the randomized results hold against oblivious adversaries. Apart from these techniques, we finally give a randomized memoryless replication algorithm for rings that is 4-competitive against adaptive on-line adversaries.