New On-Line Algorithms for the Page Replication Problem

✍ Scribed by Susanne Albers; Hisashi Koga

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 210 KB
• Volume: 27
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1997.0906

✦ Synopsis

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 2 c-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.