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 5m. 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 pj, 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.
