2026-07-24T10:14:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17675 2024-03-06T11:00:17Z ddc:004 open_access

Online Paging with Heterogeneous Cache Slots Chrobak, Marek Haney, Samuel Liaee, Mehraneh Panigrahi, Debmalya Rajaraman, Rajmohan Sundaram, Ravi Young, Neal E. Caching and paging algorithms k-server weighted paging laminar family It is natural to generalize the online 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 initiate a systematic study of 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-Heterogenous Paging. In realistic settings only certain subsets of cache slots or servers would appear in requests. Therefore we parameterize the problem by specifying a family 𝒮 ⊆ 2^[k] of requestable slot sets, and we establish bounds on the competitive ratio as a function of the cache size k and family 𝒮. If all request sets are allowed (𝒮 = 2^[k]), the optimal deterministic and randomized competitive ratios are exponentially worse than for standard Paging (𝒮 = {[k]}). As a function of |𝒮| and k, the optimal deterministic ratio is polynomial: at most O(k²|𝒮|) and at least Ω(√{|𝒮|}). For any laminar family {𝒮} of height h, the optimal ratios are O(hk) (deterministic) and O(h²log 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). Some results for the laminar case are shown via a reduction to the generalization of Paging in which each request specifies a set P of pages, and is satisfied by fetching any page from P into the cache. The optimal ratios for the latter problem (with laminar family of height h) are at most hk (deterministic) and hH_k (randomized). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marek Chrobak and Samuel Haney and Mehraneh Liaee and Debmalya Panigrahi and Rajmohan Rajaraman and Ravi Sundaram and Neal E. Young 2023 Is Part Of LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2023.23 urn:nbn:de:0030-drops-176759 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.23 eng https://creativecommons.org/licenses/by/4.0/legalcode