AbstractWe present the first randomized upper and lower bounds for online multi-threaded paging as introduced by Feuerstein and Strejilevich de Loma [1996]. Our main result is a O(w log k)-competitive algorithm for unfair infinite multi-threaded paging, which is optimal to within a constant factor. We also present algorithms and lower bounds for three other sub-models of multi-threaded paging.
Categories and Subject Descriptors: F.2 [Analysis of Algorithms and Problem Complexity]
Additional Key Words and Phrases: online algorithms, paging, competitive analysis
Selected references
- Rakesh Barve, Edward F. Grove, and Jeffrey Scott Vitter. Application-controlled paging for a shared cache (extended abstract). In 36th Annual Symposium on Foundations of Computer Science, pages 204-213, Milwaukee, Wisconsin, 23-25 October 1995. IEEE.
- Allan Borodin, Nathan Linial, and Michael E. Saks. An optimal on-line algorithm for metrical task system. Journal of the ACM, 39(4):745-763, October 1992.
- Amos Fiat, Richard M. Karp, Michael Luby, Lyle A. McGeoch, Daniel D. Sleator, and Neal E. Young. Competitive paging algorithms. Journal of Algorithms, 12(4):685-699, December 1991.
- Anna R. Karlin, Mark S. Manasse, Larry Rudolph, and Daniel Dominic Sleator. Competitive snoopy caching. Algorithmica, 3:77-119, 1988.
- Lyle A. McGeoch and Daniel Dominic Sleator. A strongly competitive randomized paging algorithm. Algorithmica, 6:816-825, 1991.
- Andrew Chi-Chih Yao. Probabilistic computations: Toward a unified measure of complexity (extended abstract). In 18th Annual Symposium on Foundations of Computer Science, pages 222-227, Providence, Rhode Island, 31 October-2 November 1977. IEEE.