belady-anomaly · research · also Belady's anomaly, FIFO capacity anomaly

Belady anomaly

A Belady anomaly occurs when a replacement policy produces more misses with a larger cache than with a smaller cache on the same reference string and initial-state convention.

Related Observatory article: Belady anomaly on hesela.com

Belady, Nelson and Shedler studied the FIFO case in 1969. [1]

The 2010 unboundedness result varies capacities and reference strings; it is not an unbounded ratio for fixed capacities. [2]

Relations

related
fifo-replacement, cache-inclusion-property, lru-replacement

Citations

  1. Belady, Nelson and Shedler. An anomaly in space-time characteristics of certain programs running in a paging machine. CACM, 1969. (accessed 2026-10-17)
  2. Peter Fornai and Antal Ivanyi. FIFO anomaly is unbounded. Acta Univ. Sapientiae, Informatica 2(1), 2010, pp. 80-89; sections 2-5, arXiv:1003.1336v2. (accessed 2026-10-17)
  3. Hesela: finite cache-capacity replay, with full traces and assumptions. (accessed 2026-10-17)
Sources & caveats

JSON: /data/terms/belady-anomaly.json