• • 2025Online paging with heterogeneous cache slots
  Algorithmica 87:43(2025)

  With Marek Chrobak, Samuel Haney, Mehraneh Liaee, Debmalya Panigrahi, Rajmohan Rajaraman and Ravi Sundaram
  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 $\mathcal S \subseteq 2^{[k]}$ of requestable slot sets, and we establish bounds on the competitive ratio as a function of the cache size $k$ and family $\mathcal S$:

  • If all request sets are allowed ($\mathcal S=2^{[k]}\setminus\{\emptyset\}$), the optimal deterministic and randomized competitive ratios are exponentially worse than for standard Paging ($\mathcal S=\{[k]\}$).
  • As a function of $|\mathcal S|$ and $k$, the optimal deterministic ratio is polynomial: at most $O(k^2|\mathcal S|)$ and at least $\Omega(\sqrt{|\mathcal S|})$.
  • For any laminar family $\mathcal S$ of height $h$, the optimal ratios are $O(hk)$ (deterministic) and $O(h^2\log k)$ (randomized).
  • The special case of laminar $\mathcal S$ 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. The optimal deterministic ratio for weighted All-or-One Paging is $\Theta(k)$. Offline All-or-One Paging is NP-hard.

  
  
  Some results for the laminar case are shown via a reduction to the generalization of Paging in which each request specifies a set $\mathcal P$ of pages, and is satisfied by fetching any page from $\mathcal 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).

  Journal version of [2023].

  • more...
  •   full text
    
  •   bibtex
    
  •   google scholar
    
  •   doi
    

© Copyrights are reserved by the publishers.
Download for personal and limited academic use only.