Online Paging with Heterogeneous Cache Slots

06/11/2022
by   Marek Chrobak, et al.
0

It is natural to generalize the k-Server problem by allowing each request to specify not only a point p, but also a subset S of servers that may serve it. To attack this generalization, we focus on uniform and star metrics. For uniform metrics, the problem is equivalent to a generalization of Paging in which each request specifies not only a page p, but also a subset S of cache slots, and is satisfied by having a copy of p in some slot in S. We call this problem Slot-Heterogeneous Paging. We parameterize the problem by specifying an arbitrary family S⊆ 2^[k], and restricting the sets S to S. If all request sets are allowed (S=2^[k]), the optimal deterministic and randomized competitive ratios are exponentially worse than for standard Paging (S={[k]}). As a function of | S| and the cache size k, the optimal deterministic ratio is polynomial: at most O(k^2| S|) and at least Ω(√(| S|)). For any laminar family S of height h, the optimal ratios are O(hk) (deterministic) and O(h^2log k) (randomized). The special case that we call All-or-One Paging extends standard Paging by allowing each request to specify a specific slot to put the requested page in. For All-or-One Paging the optimal competitive ratios are Θ(k) (deterministic) and Θ(log k) (randomized), while the offline problem is NP-hard. We extend the deterministic upper bound to the weighted variant of All-Or-One Paging (a generalization of standard Weighted Paging), showing that it is also Θ(k).

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset