Online Companion Caching

Details Online Companion Caching Online Companion Caching

2004-06-18

arxiv.org/abs/cs/0406036v1

Theoret. Comput. Sci. 324(2-3): 183-200, 2004

Computer Science

Data Structures and Algorithms

17 pages, 1 figure. Preliminary version in ESA '02. To be published in Theoretical Computer Science A

Scientific paper

10.1016/j.tcs.2004.05.015

This paper is concerned with online caching algorithms for the (n,k)-companion cache, defined by Brehob et. al. In this model the cache is composed of two components: a k-way set-associative cache and a companion fully-associative cache of size n. We show that the deterministic competitive ratio for this problem is (n+1)(k+1)-1, and the randomized competitive ratio is O(\log n \log k) and \Omega(\log n +\log k).

Affiliated with

Also associated with

No associations

Rating

Online Companion Caching 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 Online Companion Caching, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Online Companion Caching will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-203575