The K-Server Dual and Loose Competitiveness for Paging

Details The K-Server Dual and Loose Competitiveness for Paging The K-Server Dual and Loose Competitiveness for Paging

2002-05-18

arxiv.org/abs/cs/0205044v1

Algorithmica 11(6):525-541 (1994)

Computer Science

Data Structures and Algorithms

conference version: "On-Line Caching as Cache Size Varies", SODA (1991)

Scientific paper

This paper has two results. The first is based on the surprising observation that the well-known ``least-recently-used'' paging algorithm and the ``balance'' algorithm for weighted caching are linear-programming primal-dual algorithms. This observation leads to a strategy (called ``Greedy-Dual'') that generalizes them both and has an optimal performance guarantee for weighted caching. For the second result, the paper presents empirical studies of paging algorithms, documenting that in practice, on ``typical'' cache sizes and sequences, the performance of paging strategies are much better than their worst-case analyses in the standard model suggest. The paper then presents theoretical results that support and explain this. For example: on any input sequence, with almost all cache sizes, either the performance guarantee of least-recently-used is O(log k) or the fault rate (in an absolute sense) is insignificant. Both of these results are strengthened and generalized in``On-line File Caching'' (1998).

Affiliated with

Also associated with

No associations

Rating

The K-Server Dual and Loose Competitiveness for Paging does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The K-Server Dual and Loose Competitiveness for Paging, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The K-Server Dual and Loose Competitiveness for Paging will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-599177