Online Paging with Heterogeneous Cache Slots

Abstract It is natural to generalize the online $$k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>k</mml:mi> </mml:math> -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 date, only a few special cases of this problem have been studied. The objective of the work presented in this paper has been to more systematically explore this generalization in the case of 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]}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>S</mml:mi> <mml:mo>⊆</mml:mo> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow> <mml:mo>[</mml:mo> <mml:mi>k</mml:mi> <mml:mo>]</mml:mo> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> of requestable slot sets, and we establish bounds on the competitive ratio as a function of the cache size k and family $${\mathcal {S}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>S</mml:mi> </mml:math> : If all request sets are allowed ( $${\mathcal {S}}=2^{[k]}\setminus \{\emptyset \}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>S</mml:mi> <mml:mo>=</mml:mo> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow> <mml:mo>[</mml:mo> <mml:mi>k</mml:mi> <mml:mo>]</mml:mo> </mml:mrow> </mml:msup> <mml:mo>\</mml:mo> <mml:mrow> <mml:mo>{</mml:mo> <mml:mi>∅</mml:mi> <mml:mo>}</mml:mo> </mml:mrow> </mml:mrow> </mml:math> ), the optimal deterministic and randomized competitive ratios are exponentially worse than for standard Paging ( $${\mathcal {S}}=\{[k]\}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>S</mml:mi> <mml:mo>=</mml:mo> <mml:mo>{</mml:mo> <mml:mo>[</mml:mo> <mml:mi>k</mml:mi> <mml:mo>]</mml:mo> <mml:mo>}</mml:mo> </mml:mrow> </mml:math> ). As a function of $$|{\mathcal {S}}|$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>|</mml:mo> <mml:mi>S</mml:mi> <mml:mo>|</mml:mo> </mml:mrow> </mml:math> and k , the optimal deterministic ratio is polynomial: at most $$O(k^2|{\mathcal {S}}|)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>k</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>|</mml:mo> <mml:mi>S</mml:mi> <mml:mo>|</mml:mo> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> and at least $$\Omega (\sqrt{|{\mathcal {S}}|})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Ω</mml:mi> <mml:mo>(</mml:mo> <mml:msqrt> <mml:mrow> <mml:mo>|</mml:mo> <mml:mi>S</mml:mi> <mml:mo>|</mml:mo> </mml:mrow> </mml:msqrt> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . For any laminar family $${\mathcal {S}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>S</mml:mi> </mml:math> of height h , the optimal ratios are O ( hk ) (deterministic) and $$O(h^2\log k)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>h</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>log</mml:mo> <mml:mi>k</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> (randomized). The special case of laminar $${\mathcal {S}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>S</mml:mi> </mml:math> 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)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Θ</mml:mi> <mml:mo>(</mml:mo> <mml:mi>k</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . Offline All-or-One Paging is <jats:alternati