Adversarial models in paging

The classical online paging problem mathematically abstracts memory management systems. Early worst-case results for paging algorithms leave a significant gap to practical experience: Many “reasonable” algorithms, such as Least Recently Used, are empirically superior to “intuitively inferior” ones, like First-In First-Out or Flush When Full. But they have identical theoretical worst-case performance guarantees. Moreover, these guarantees do not adequately reflect empirical evidence. To overcome this unsatisfying situation, many adversarial models intended to reflect the “typical” situation have been proposed. This article surveys the most prominent of them.