Online Parallel Paging with Optimal Makespan

The classical paging problem can be described as follows: given a cache that can hold up to k pages (or blocks) and a sequence of requests to pages, how should we manage the cache so as to maximize performance-or, in other words, complete the sequence as quickly as possible. Whereas this sequential paging problem has been well understood for decades, the parallel version, where the cache is shared among p processors each issuing its own sequence of page requests, has been much more resistant. In this problem we are given p request sequences R1, R2, ?, Rp, each of which accesses a disjoint set of pages, and we ask the question: how should the paging algorithm manage the cache to optimize the completion time of all sequences (i.e., the makespan). As for the classical sequential problem, the goal is to design an online paging algorithm that achieves an optimal competitive ratio, using O(1) resource augmentation. In a recent breakthrough, Agrawal et al. [SODA '21] showed that the optimal (deterministic) competitive ratio C for this problem is in the range O(log p) = C = O(log2 p). This paper closes that gap, showing how to achieve a competitive ratio C = O(log p). Our techniques reveal surprising combinatorial differences between the problem of optimizing makespan and that of optimizing the closely related metric of mean completion time; and yet our algorithm manages to be simultaneously asymptotically optimal for both tasks.