Source-linked AI summary
Dependency-Aware Online Caching
Julien Dallot, Amirmehdi Jafari Fesharaki, Maciej Pacut, Stefan Schmid
TL;DR
Dependency-aware caching requires an item’s dependencies to remain cached with it, complicating eviction. The paper develops randomized online algorithms for caching with dependencies, including bypassing, and proves competitive bounds for both settings.
Problem
In dependency-aware caching, an item can reside in the cache only when all its dependent items are also cached, making eviction decisions more constrained than in classic caching.
Source: §1 · pp. 1–2Method
The paper develops randomized Bucketing algorithms for dependency-aware caching and extends the procedure to bypassing, where requests can be served for a fixed price without fetching items into the cache.
Source: §1 · pp. 2–3Results
Bucketing is O(log k)-competitive, while BucketingBypass is O(√k · log k)-competitive, significantly improving the best known competitiveness for bypassing.
Source: §1 · pp. 2–3Takeaways & Limitations
The paper identifies weighted caching and file caching as future settings for studying dependencies.
Source: §7 · p. 19Recursive LRU works for the deterministic case only and does not achieve optimal competitiveness for randomized algorithms.
Source: §4.4 · p. 14
Abstract
from arXiv · showhide
We consider a variant of the online caching problem where the items exhibit dependencies among each other: an item can reside in the cache only if all its dependent items are also in the cache. The dependency relations can form any directed acyclic graph. These requirements arise e.g., in systems such as CacheFlow (SOSR 2016) that cache forwarding rules for packet classification in IP-based communication networks. First, we present an optimal randomized online caching algorithm which accounts for dependencies among the items. Our randomized algorithm is $O( \log k)$-competitive, where $k$ is the size of the cache, meaning that our algorithm never incurs the cost of $O(\log k)$ times higher than even an optimal algorithm that knows the future input sequence. Second, we consider the bypassing model, where requests can be served at a fixed price without fetching the item and its dependencies into the cache -- a variant of caching with dependencies introduced by Bienkowski et al. at SPAA 2017. For this setting, we give an $O( \sqrt{k \cdot \log k})$-competitive algorithm, which significantly improves the best known competitiveness. We conduct a small case study, to find out that our algorithm incurs on average 2x lower cost.
1 Introduction
The paper formalizes online caching with DAG dependencies, motivated by packet-classification rules that cannot be cached independently. It presents competitive algorithms for settings with and without bypassing, characterizes graph effects, and reports a case study.
1 Introduction
- Dependency-aware caching requires every cached item’s dependencies to remain cached, constraining evictions and making classic dependency-unaware algorithms potentially infeasible.The paper models dependencies as an arbitrary directed acyclic graph and seeks to minimize fetches.Source: §1 · pp. 1–2
1.1 Motivation: Packet Classification
- Overlapping packet-classification rules require a higher-priority rule to be cached whenever an overlapping lower-priority rule is cached; multi-field and wildcard rules can create DAG dependencies.The paper frames this setting as a rigorous alternative to CacheFlow.Source: §1 · p. 1, §1.1 · p. 3
1.2 Related Work
- Bienkowski et al. introduce online tree caching, an online dependency-aware caching variant restricted to binary trees, where bypass is allowed and their algorithm achieves an O(k · h(T)) competitive ratio, with h(T) the dependency-tree height.Source: §1.2 · p. 4
1.3 Contributions
- Without bypassing, Recursive LRU is k-competitive and randomized Bucketing is 2H_k-competitive; Bucketing’s ratio is 2H_min{k,ℓ}, with ℓ the maximum independent-set size in the transitive closure.The paper proves no randomized algorithm can beat H_min{k,ℓ}, making its randomized algorithm asymptotically optimal, including for tree dependencies [32].Source: §1.3 · p. 4
- For bypassing, the paper gives a (6√k · H_min{k,ℓ})-competitive algorithm, improving on the prior O(k · h(T)) bound and making the ratio independent of graph height.The new ratio can improve further when dependency-graph properties are accounted for.Source: §1.3 · p. 4
- In a case study, the randomized algorithm averages 2x lower cost per request than TreeCaching.Source: §1.3 · p. 5
2 Organization
The paper outlines its progression from the problem model to algorithm analyses, then to bypassing and empirical evaluation.
2 Organization
- Section 3 defines the problem and introduces notation used throughout the paper.Source: §2 · p. 5
- Section 4 presents the main randomized algorithm, analyzes its competitiveness, and also gives a deterministic algorithm and lower bounds.Source: §2 · p. 5
- Section 5 treats randomized caching with bypassing, and the paper concludes with empirical evidence against Zipfian and Exponential distributions.Source: §2 · p. 5
3 Preliminaries
The model is an online two-level memory hierarchy with a capacity-limited cache and DAG dependencies that restrict feasible cache states.
3.1 Model
- The system has slow memory containing the universe and fast memory holding at most k items, where k ≥ 1.Source: §3.1 · p. 5
- Dependencies form an arbitrary DAG, and an item may be cached only if all items reachable from it are also cached; each item has at most k − 1 dependencies.Source: §3.1 · p. 5
- On a request miss, the algorithm fetches the item and any absent dependencies, may evict other items to make room, and aims to minimize fetches.Source: §3.1 · p. 5
3.2 Notation
- T(x) denotes x and all its descendants, which are precisely its dependencies; the paper fixes a total item order consistent with a reversed topological order.Source: §3.2 · p. 5
- For a DAG, the paper defines its maximum independent set using the symmetric closure of its transitive closure.Source: §3.2 · p. 5
4 Dependency-Aware Caching without Bypassing
This section studies algorithms for dependency-aware caching without bypassing, presenting randomized Bucketing alongside a deterministic recursive algorithm. It describes their competitiveness guarantees in relation to cache size and dependency-graph structure, including the deterministic algorithm’s k-competitiveness and optimality among deterministic algorithms.
4 Dependency-Aware Caching without Bypassing
- The section introduces Bucketing as a randomized algorithm whose expected competitive ratio is below 2H_min{k,ℓ}, and says an asymptotically tight lower bound establishes its optimality.Here ℓ is the maximum independent-set size in the transitive closure of the dependency graph.Source: §4 · p. 6
4.1 The Randomized Algorithm Bucketing
- Bucketing forms buckets from cached items whose maximum-τ item can be evicted feasibly, then chooses a bucket uniformly at random when an eviction is needed.It considers missing items in increasing τ order and starts a new phase when the bucket pool empties.Source: §4.1 · pp. 6–7
4.2 Proof for the competitiveness of Bucketing
- Section 4.2 states that Bucketing has expected competitive ratio H_min{k,ℓ} against the oblivious adversary.The later theorem in Section 4.2.3 states a 2H_min{k,ℓ} ratio.Source: §4.2 · p. 8, §4.2.3 · p. 11
4.2.1 Upper Bound for the Bucketing Algorithm
- Bucketing’s phase analysis bounds expected fetches by H_min{k,ℓ} times the number of clean fetches, with k the cache size and ℓ the maximum independent-set size in the transitive closure.The analysis divides phases into fragments separated by bucket-freeze events.Source: §4.2.1 · pp. 8, 11
4.2.2 A Lower Bound for any Algorithm in a Phase
- The phase lower-bound argument synchronizes an offline optimum with Bucketing by ordering each request’s evictions before its τ-ordered fetches, including when a phase ends mid-request.The synchronized OPTτ remains feasible and has the same cost as OPT.Source: §4.2.2 · p. 11
4.2.3 Bounding the Competitive Ratio
- Bucketing is 2H_min{k,ℓ}-competitive against an oblivious adversary, where ℓ is the maximum independent-set size in the dependency graph’s transitive closure.The theorem states that this result is tight with the lower bound in the next subsection.Source: §4.2.3 · p. 11
4.3 A Lower Bound for Dependency-Aware Caching without Bypassing
- The lower bound shows that no randomized online algorithm can achieve a ratio better than H_min{k,ℓ} against an oblivious adversary.The construction uses a graph with isolated nodes and a chain; its request phases correspond to a random walk that must visit all nodes of a complete graph.Source: §4.3 · p. 12
4.4 Deterministic Algorithm Recursive LRU
- Recursive LRU is k-competitive and optimal: it updates timestamps top-to-bottom, then fetches dependencies bottom-to-top to preserve cache feasibility.The paper’s deterministic lower bound for classic caching also applies to dependency-aware caching.Source: §4.4 · p. 13
- DET pays at most k per phase while OPT pays at least 1, making DET k-competitive.Source: §4.4 · p. 14
- Because deterministic algorithms for classic caching have a competitiveness lower bound of k [5], DET is optimal among deterministic algorithms for dependency-aware caching.Source: §4.4 · p. 14
- Recursively applying a known classic-caching algorithm works for the deterministic case only and does not yield optimal competitiveness for randomized algorithms.Source: §4.4 · p. 14
5 Dependency-Aware Caching with Bypassing
BucketingBypass extends randomized dependency-aware caching to requests that may instead be served at a fixed bypass cost. Its phase-cost analysis and offline lower bounds yield a competitive-ratio guarantee against the oblivious adversary.
5.1.1 Presentation of the algorithm BucketingBypass
- BucketingBypass adapts the randomized eviction procedure of Bucketing to use bypassing, which serves a request for cost 1 without fetching the item or its dependencies.If fetched, the requested item and its missing dependencies enter the cache; later requests are free until the cache changes.Source: §5 · p. 14, §5.1.1 · p. 14
5.1.2 Upper-bound on the cost of BucketingBypass
- For each phase, its expected cost is at most 2Hmin{k,ℓ} · C + pk · Hmin{k,ℓ}, where C is the number of clean requests.The analysis bounds bypassed requests separately from requests handled through fetching.Source: §5.1.2 · p. 16
5.2 A Lower Bound for Any Offline Algorithm and Bounding the Ratio
- The offline comparison uses OPTτ, which preserves OPT’s cost while ordering fetches by increasing τ after its evictions.A second lower bound handles phases with zero clean fetches, complementing the bound proportional to their number.Source: §5.2 · pp. 16–17
- BucketingBypass is 6pk · Hmin{k,ℓ}-competitive against the oblivious adversary, where ℓ is the maximum independent-set size in the transitive closure and k is cache size.The guarantee combines amortized lower bounds on the offline algorithm’s cost across phases.Source: §5.2 · pp. 16–17
6 Evaluations
The evaluation compares BucketingBypass with TreeCaching on balanced binary-tree requests under Zipf and geometric distributions. BucketingBypass has lower mean cost per request across the inspected cache sizes.
6 Evaluations
- The comparison uses TreeCaching because it shares the objective of optimizing cache-change costs, unlike CacheFlow, which does not account for that cost.The paper also contrasts the algorithms’ analytical bounds: 6√k · Hk for BucketingBypass and O(h(T) · k) for TreeCaching.Source: §6 · p. 18
- The evaluation generates 5000-request sequences under Zipf and exponential distributions, averages results over 10 repetitions, and measures mean cost per request.Requests are assigned by tree level and then uniformly among items at that level; requests that cannot fit are pruned by rejection sampling.Source: §6 · pp. 18–19
- BucketingBypass incurs on average 2x lower cost per request than TreeCaching across the inspected cache sizes.Figure 3 compares cost per request for a binary tree with height 10 and 1023 nodes, using Zipf (a=4) and geometric (p=10) distributions.Source: Figure 3 · p. 18, §6 · p. 19
7 Conclusions and Future Directions
The paper concludes with competitive caching algorithms that account for dependencies among items and identifies weighted and file caching as directions for future study.
7 Conclusions and Future Directions
- The paper proposes several competitive caching algorithms that account for dependencies among items.Source: §7 · p. 19
- Future work could study dependency aspects in more general variants, including weighted caching and file caching.Source: §7 · p. 19
- The authors made their code and evaluation artefacts publicly available to support further research and reproducibility.Source: §7 · p. 19