License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2023.23
URN: urn:nbn:de:0030-drops-176759
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17675/
Chrobak, Marek ;
Haney, Samuel ;
Liaee, Mehraneh ;
Panigrahi, Debmalya ;
Rajaraman, Rajmohan ;
Sundaram, Ravi ;
Young, Neal E.
Online Paging with Heterogeneous Cache Slots
Abstract
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).
BibTeX - Entry
@InProceedings{chrobak_et_al:LIPIcs.STACS.2023.23,
author = {Chrobak, Marek and Haney, Samuel and Liaee, Mehraneh and Panigrahi, Debmalya and Rajaraman, Rajmohan and Sundaram, Ravi and Young, Neal E.},
title = {{Online Paging with Heterogeneous Cache Slots}},
booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
pages = {23:1--23:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-266-2},
ISSN = {1868-8969},
year = {2023},
volume = {254},
editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17675},
URN = {urn:nbn:de:0030-drops-176759},
doi = {10.4230/LIPIcs.STACS.2023.23},
annote = {Keywords: Caching and paging algorithms, k-server, weighted paging, laminar family}
}
|
Keywords: |
|
Caching and paging algorithms, k-server, weighted paging, laminar family |
|
Collection: |
|
40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
03.03.2023 |
