NEW ONLINE ALGORITHMS FOR THE PAGE REPLICATION PROBLEM

We present improved competitive on-line algorithms for the page replic ation problem and concentrate on important network topologies for whic h algorithms with a constant competitive ratio can be given. We develo p an optimal randomized on-line replication algorithm for trees and un iform networks; its competitive ratio is approximately 1.58. This perf ormance 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 o n-line algorithm for rings that is 3.16-competitive. We also derive tw o 4-competitive on-line algorithms for rings which are either determin istic or randomized and memoryless. Again, the randomized results hold against oblivious adversaries. Apart from these techniques, we finall y give a randomized memoryless replication algorithm for rings that is 4-competitive against adaptive on-line adversaries. (C) 1998 Academic Press.