neal young / Chrobak23Online

• 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).