New and Improved Bounds for Markov Paging

Chirag Pabbaraju, Ali Vakilian · 2025

Read New and Improved Bounds for Markov Paging by Chirag Pabbaraju, Ali Vakilian (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-05511.txt.

Description

Chirag Pabbaraju and Ali Vakilian wrote this 2025 theory paper on paging, the task of keeping the most useful pages in a small fast cache. In the Markov version of the task, page requests follow a chance pattern with memory, and the goal is few cache misses on average. A classic method from 1994 was long known to cost at most four times the best possible offline cost.

The authors sharpen the proof for that classic method and show it is in fact at most twice the best cost. They also prove a lower bound: no run of the method can promise better than about 1.59 times the best cost in the worst case. No such lower bound was known before, so the work closes much of the gap on this method.

Catalog record

CREATORChirag Pabbaraju, Ali Vakilian
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE80 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-05511

Browse the full library · About the Tower of Babel