On-Line caching tis Cache
Neal E. Young · 1991
Reconsider the competitiveness ofon-line strategies using k servers versus the optimal off-line strategy using h S k servers for the paging, weighted cache, and k-server problems. We show that when h e, and at most 2 otherwise. We show this is roughly within a factor of two of optimal. Intuitively, we say a paging strategy is loosely Competitive if, for any sequence, at most cache sizes the fault rate of the pa ing strategy is at most an insignificant 7 amount above C(k times the fault rate of the optimal strategy. We show that LRU, FWF, and FIFO are loosely C’(k)-competitive provided C(k)/ in k ~ co and that the marking algorithm is loosely C(k) -competitive provided C(k) ‐21nlnk~ co. We formulate the off-line version of the k-server problem as a linear program and examine the dual to derive a lower bound on the performance of the optimal algorithm. We use this bound to show that for the weighted cache prc~blem the balance algorithm is --competitive.