论文标题
与异构缓存插槽的在线要求
Online Paging with Heterogeneous Cache Slots
论文作者
论文摘要
通过允许每个请求不仅指定点$ p $，而且还可以为其提供服务的服务器的子集$ S $，从而概括在线$ k $ - 服务器问题是很自然的。对于统一的指标，问题等同于分页的概括，其中每个请求不仅指定了$ p $，还指定了一个子集$ s $的缓存插槽，并且可以通过在$ s $中的某个插槽中获得$ p $的副本来满足。我们称此问题的插槽 - 生态分页。 我们通过指定一个家庭$ \ Mathcal S \ subseteq 2^{[k]} $来参数化问题，并且我们根据竞争比率建立界限，这是缓存尺寸$ k $和family $ \ Mathcal S $的函数的范围。 - 如果允许所有请求集（$ \ MATHCAL S = 2^{[[K]} \ setMinus \ {\ emptySet \} $），则最佳确定性和随机竞争比率比标准\ paging（$ \ m nathcal s = \ {k] [[k] \} $比标准\ paging（$ \ mathcal s = \} $）。 - 作为$ | \ MATHCAL S | $和$ K $的函数，最佳确定比率是多项式：最多$ O（K^2 | \ Mathcal S |）$和至少$ω（\ sqrt {| \ Mathcal s |}）$。 - 对于任何laminar家族$ \ MATHCAL S $ of HEIGHT $ H $，最佳比率为$ O（HK）$（确定性）和$ O（H^2 \ log K）$（随机）。 - 我们称之为全或一个分页的laminar $ \ Mathcal S $的特殊情况通过允许每个请求来指定特定的插槽以将请求的页面放入。加权的全或一对一分页的最佳确定比率为$θ（k）$。脱机全或一个分页是NP-HARD。 层流案例的一些结果是通过减少分页的概括来显示的，其中每个请求指定了一个集合的$ \ MATHCAL P，并且可以通过将任何页面从$ \ MATHCAL P中获取到缓存中来满足。后一个问题的最佳比率（带有laminar的高度$ 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 $Ω(\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 $Θ(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).
