farthest-in-future-replacement · research · also Farthest-next-use replacement, Belady replacement, OPT replacement

Farthest-in-future replacement

Farthest-in-future replacement evicts a resident object whose next request is latest in a known future reference string.

Related Observatory article: Farthest-in-future replacement on hesela.com

For equal-size demand paging and unit miss cost, the rule is optimal but requires future references. Mattson et al. call it OPT, distinguishing it from the earlier MIN. [1]

With unequal-size objects, repeatedly applying the rule need not minimize misses. The comparator must use the same bypass/admission contract. [2]

FOO's finite-trace lower/upper bounds do not require independent references; independence and nonconcentration enter its separate asymptotic-tightness theorem. Correlation does not itself invalidate the bracket, but a narrow gap is not guaranteed. The caching model must still match. [2]

For ABCDCAB, A=2, B=C=D=1 and capacity 3 size units, mandatory farthest-next-use misses six times; an exact plan misses five times. These are constructed requests. [3]

For ABCABC, A=3, B=C=1, capacity 3 and bypass allowed, minimizing requests gives four misses/eight fetched units; minimizing payload gives five misses/seven fetched units. No plan achieves both minima. [3]

FOO's interval objective excludes first-reference cost. In ABCDCAB, four compulsory misses leave two versus one repeat misses over three repeat requests; totals stay six versus five. Subtracting this constant preserves the optimizer, not relative reductions or denominators. This is not a warm-start experiment. [2] [3]

An immediate-fill miss bound is not a delayed-fill latency bound. Fetch timing and joined requests need a separate state model and objective. [4]

Relations

related

Cache inclusion property, Belady anomaly, Least recently used replacement, Cache admission, Delayed cache hit

Limitations

• Optimality is specific to an objective and model; future knowledge does not imply minimum latency or device I/O.

Citations

1. Mattson et al. Evaluation techniques for storage hierarchies. IBM Systems Journal 9(2), 1970, pp. 93-95. DOI 10.1147/sj.92.0078. (accessed 2026-11-06)
2. Berger et al. Practical Bounds on Optimal Caching with Variable Object Sizes. POMACS 2(2), 2018, article 32. DOI 10.1145/3224427. (accessed 2026-11-06)
3. Hesela: offline-bound calculation, resident-state witnesses and controls. (accessed 2026-11-06)
4. Keerthana Gurushankar, Noah G. Singer and Bernardo Subercaseaux. Latency Guarantees for Caching with Delayed Hits. arXiv:2501.16535v1, 2025; section 2. (accessed 2026-11-06)

JSON: /data/terms/farthest-in-future-replacement.json