Online Paging with Heterogeneous Cache Slots
Online Paging with Heterogeneous Cache Slots
复制标题
DOI：
10.48550/arxiv.2206.05579
复制
发表时间：
2022-06
期刊：
影响因子：
--
通讯作者：
M. Chrobak;Samuel Haney;Mehraneh Liaee;Debmalya Panigrahi;R. Rajaraman;Ravi Sundaram;N. Young
中科院分区：
文献类型：
--
作者：
M. Chrobak;Samuel Haney;Mehraneh Liaee;Debmalya Panigrahi;R. Rajaraman;Ravi Sundaram;N. Young
通过允许每个请求不仅指定一个点$p$，而且指定可能为其服务的服务器的子集$S$，来推广在线$k$-服务器问题是很自然的。对于统一度量，该问题等价于分页的推广，其中每个请求不仅指定页面$p$，而且指定缓存槽的子集$S$，并且通过在$S$中的某个槽中具有$p$的副本来满足。我们把这个问题称为时隙异构寻呼。我们通过指定可请求插槽集的系列$\mathcal S \subseteq 2^{[k]}$来参数化该问题，并且我们将竞争比的界限建立为该高速缓存大小$k$和系列$\mathcal S$的函数：- 如果允许所有请求集（$\mathcal S=2^{[k]}\setminus\{\emptyset\}$），最优的确定性和随机化竞争比比对于标准寻呼（$\mathcal S=\{[k]\}$）指数地更差。- 作为$的函数|\mathcal S| $和$k$，最优确定性比率是多项式的：至多$O（k^2|\mathcal S|）$和至少$\Omega（\sqrt{|\mathcal S|})$. - 对于任何高度为h的层流族\mathcal S，最优比例为O（hk）（确定性）和O（h^2\log k）（随机性）。- 我们称之为All-or-One Paging的laminar $\mathcal S$的特殊情况扩展了标准Paging，允许每个请求指定一个特定的插槽来放置所请求的页面。加权全或一寻呼的最佳确定性比率是$\Theta（k）$。离线All-or-One寻呼是NP难的。层状情况下的一些结果显示通过减少到一般的分页，其中每个请求指定一组$\mathcal P的页面，并通过获取任何页面从$\mathcal P到该高速缓存。后一个问题的最优比率（具有高度为h$的层流族）至多为$hk$（确定性）和$h\，H_k$（随机性）。
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. 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. 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 $h\,H_k$ (randomized).