Nikhil Bansal
Abstract
We study the weighted version of the classic online paging problem where there is a weight (cost) for fetching each page into the cache. We design a randomized O(log k)-competitive online algorithm for this problem, where k is the cache size. This is the first randomized o(k)-competitive algorithm and its competitive ratio matches the known lower bound for the problem, up to constant factors. More generally, we design an O(log(k/(k − h + 1)))-competitive online algorithm for the version of the problem where the online algorithm has cache size k and it is compared to an optimal offline solution with cache size h ≤ k.
Our solution is based on a two-step approach. We first obtain an O(log k)-competitive fractional algorithm based on an online primal-dual approach. Next, we obtain a randomized algorithm by rounding in an online manner the fractional solution to a probability distribution on the possible cache states. We also give an online primal-dual randomized O(log N)-competitive algorithm for the Metrical Task System problem (MTS) on a weighted star metric on N leaves.
- Achlioptas, D., Chrobak, M., and Noga, J. 2000. Competitive analysis of randomized paging algorithms. Theoret. Computer Science 234, 1--2, 203--218. Google Scholar
Digital Library
- Adamaszek, A., Czumaj, A., Englert, M., and Räcke, H. 2012. An O(log k)-competitive algorithm for generalized caching. In SODA. 1681--1689. Google ScholarDigital Library
- Albers, S. 2003. Online algorithms: A survey. Math. Prog. 97, 3--26.Google ScholarCross Ref
- Bansal, N., Buchbinder, N., Madry, A., and Naor, J. 2011. A polylogarithmic-competitive algorithm for the k-server problem. In Proceedings of the Symposium on Foundations of Computer Science. 267--276. Google ScholarDigital Library
- Bansal, N., Buchbinder, N., and Naor, J. S. 2008. Randomized competitive algorithms for generalized caching. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing. 235--244. Google ScholarDigital Library
- Bar-Noy, A., Bar-Yehuda, R., Freund, A., Naor, J. S., and Schieber, B. 2001. A unified approach to approximating resource allocation and scheduling. J. ACM 48, 5, 1069--1090. Google ScholarDigital Library
- Bartal, Y., Blum, A., Burch, C., and Tomkins, A. 1997. A polylog(n)-competitive algorithm for metrical task systems. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing. 711--719. Google ScholarDigital Library
- Blum, A., Furst, M., and Tomkins, A. 1996. What to do with your free time: Algorithms for infrequent requests and randomized weighted caching. Manuscript. (www.cs.cmu.edu)Google Scholar
- Borodin, A. and El-Yaniv, R. 1998. Online computation and competitive analysis. Cambridge University Press. Google ScholarDigital Library
- Borodin, A., Linial, N., and Saks, M. E. 1992. An optimal on-line algorithm for metrical task system. J. ACM 39, 4, 745--763. Google ScholarDigital Library
- Buchbinder, N., Jain, K., and Naor, J. S. 2007. Online primal-dual algorithms for maximizing ad-auctions revenue. In Proceedings of the 15th Annual European Symposium. 253--264. Google ScholarDigital Library
- Buchbinder, N. and Naor, J. 2005. Online primal-dual algorithms for covering and packing problems. In Proceedings of the 13th Annual European Symposium on Algorithms. 689--701. Google ScholarDigital Library
- Buchbinder, N. and Naor, J. 2006. Fair online load balancing. In Proceedings of the 18th ACM Symposium on Parallelism in Algorithms and Architectures. 291--298. Google ScholarDigital Library
- Buchbinder, N. and Naor, J. 2009. The design of competitive online algorithms via a primal-dual approach. Found. Trends Theoret. Comput. Sci. 3, 2--3, 93--263. Google ScholarDigital Library
- Chrobak, M., Karloff, H., Payne, T., and Vishwanathan, S. 1991. New results on server problems. SIAM J. Disc. Math 4, 2, 172--181. Google ScholarDigital Library
- Chrobak, M. and Larmore, L. L. 1991. An optimal on-line algorithm for k-servers on trees. SIAM J. Comput. 20, 1, 144--148. Google ScholarDigital Library
- Cohen, E. and Kaplan, H. 1999. LP-based analysis of greedy-dual-size. In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms. 879--880. Google ScholarDigital Library
- Coté, A., Meyerson, A., and Poplawski, L. 2008. Randomized k-server on hierarchical binary trees. In STOC’08: Proceedings of the 40th Annual ACM Symposium on Theory of Computing. 227--234. Google ScholarDigital Library
- Fiat, A., Karp, R. M., Luby, M., McGeoch, L. A., Sleator, D. D., and Young, N. E. 1991. Competitive paging algorithms. J. Algorithms 1, 4, 685--699. Google ScholarDigital Library
- Fiat, A. and Mendel, M. 2003. Better algorithms for unfair metrical task systems and applications. SIAM J. Comput. 32, 6, 1403--1422. Google ScholarDigital Library
- Fiat, A., Rabani, Y., and Ravid, Y. 1994. Competitive k-server algorithms. J. Comput. Syst. Sci. 48, 3, 410--428. Google ScholarDigital Library
- Irani, S. 1997. Page replacement with multi-size pages and applications to web caching. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing. 701--710. Google ScholarDigital Library
- Irani, S. 2002. Randomized weighted caching with two page weights. Algorithmica 32, 4, 624--640.Google ScholarDigital Library
- Koutsoupias, E. and Papadimitriou, C. H. 1995. On the k-server conjecture. J. ACM 42, 5, 971--983. Google ScholarDigital Library
- Manasse, M. S., McGeoch, L. A., and Sleator, D. D. 1990. Competitive algorithms for server problems. J. Algorithms 11, 2, 208--230. Google ScholarDigital Library
- McGeoch, L. A. and Sleator, D. D. 1991. A strongly competitive randomized paging algorithm. Algorithmica 6, 6, 816--825.Google ScholarDigital Library
- Sleator, D. D. and Tarjan, R. E. 1985. Amortized efficiency of list update and paging rules. Commun. ACM 28, 2, 202--208. Google ScholarDigital Library
- Young, N. 1991. On-line caching as cache size varies. In SODA’91: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms. 241--250. Google ScholarDigital Library
- Young, N. E. 1994. The k-server dual and loose competitiveness for paging. Algorithmica 11, 6, 525--541.Google ScholarDigital Library
Index Terms
- A Primal-Dual Randomized Algorithm for Weighted Paging
Recommendations
Efficient Online Weighted Multi-Level Paging
SPAA '21: Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and ArchitecturesWe study the writeback-aware caching problem, a variant of classic paging where paging requests that modify data and requests that leave data intact are treated differently. We give an O(łog^2 k) competitive randomized algorithm, answering an open ...
Randomized competitive algorithms for generalized caching
STOC '08: Proceedings of the fortieth annual ACM symposium on Theory of computingWe consider online algorithms for the generalized caching problem. Here we are given a cache of size k and pages with arbitrary sizes and fetching costs. Given a request sequence of pages, the goal is to minimize the total cost of fetching the pages ...
A Primal-Dual Randomized Algorithm for Weighted Paging
FOCS '07: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer ScienceIn the weighted paging problem there is a weight (cost) for fetching each page into the cache. We design a randomized {\rm O}(\log k)-competitive online algorithm for the weighted paging problem, where k is the cache size. This is the first randomized o(...
Reviews
Gabriel Mateescu
Paging is a memory management technique where memory is divided into chunks of constant size called pages. A two-level memory system consists of a small fast memory (the cache) that can hold k pages and a large slow memory that holds n > k pages. A paging algorithm serves a sequence s of requests to the memory pages. According to the authors, if a requested page is not in the cache, a page fault occurs. The missing page must be loaded into the cache from slow memory; moreover, if all of the k pages in the cache are used, one of them must be evicted from the cache to make room for the new page. The paging algorithm decides which page to evict; this decision is made online, without knowledge of future requests. In the unweighted paging problem, the goal is to minimize the number of page faults. Each page i is associated with a positive weight w ? 1, denoting the cost of fetching the page into the cache. The goal is to minimize the cost of moving pages between the cache and slow memory. An online paging algorithm A is c -competitive with respect to the optimum offline algorithm OPT if there exists a constant b such that A ( s ) ? c OPT ( s ) + b , for any sequence s of page references, where A and OPT denote the costs of the two algorithms; c is called the competitive ratio. Prior work on online paging has generated k -competitive deterministic algorithms for the weighted paging problem, but no o ( k )-competitive randomized algorithms were known for weighted paging. This paper presents a randomized online algorithm with sublinear competitiveness for the weighted paging problem. According to the abstract, the authors have designed "a randomized O (log k )-competitive online algorithm for [the weighted paging] problem. ... This is the first randomized o ( k )-competitive algorithm, and its competitive ratio matches the known lower bound for the problem." The paging algorithm proposed by the authors consists of two main steps: "obtain an O (log k )-competitive fractional algorithm based on an online primal-dual approach[, and then] obtain a randomized algorithm online by rounding ... the fractional solution to a probability distribution on ... cache states." The solution to the primal-dual program provides a fractional view, whereby the algorithm maintains a distribution P on pages with total mass k . The randomized algorithm is obtained by transforming a fractional solution to a distribution D on cache states. The authors construct a mapping from a distribution P on the pages to an actual distribution D on cache states, such that any fractional move with cost m is mapped to a move on actual distributions with cost at most 5 m . So the randomized algorithm is still O (log k )-competitive. The topic tackled by the authors is difficult, so a careful mathematical notation is essential to understanding the work. Unfortunately, the authors use a negligent notation that makes the paper hard to read. In section 2, memory pages are denoted by p j , where j denotes the time of access. Later in the same section, j refers to how many times a page has been requested, and pages are denoted by the symbol i . Moreover, time is denoted by t instead of j . Further on in section 2, i and j change meaning again, referring to points in a metric space. The result presented is significant, being the first o ( k )-competitive randomized algorithm for weighted paging. However, the cost incurred by the algorithm in computing the fractional solution is important, and it is further magnified five times when computing the cache state distribution consistent with the page distribution. Overall, this paper represents a significant contribution, which is diminished by the poor mathematical notation. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments