Technical Report CS0692

Authors: E. Dichterman
PDF - RevisedCS0692.revised.pdf
Abstract: We study three randomized paging algorithms, using two different measures for their performances. One of the measures is the competitive ratio which was introduced by Sleator and Tarjan [ST85]. Although it is well-motivated, Ben-David and Borodin [BDB] have recently demonstrated some counter-intuitive features of this measure (concerning the roles of memory and finite lookahead in online algorithms), and have suggested an alternative measure based on the worst-case amortized cost, which is the second measure we use. We show a lower bound of this measure for paging algorithms and present an algorithm which achieves this bound. Since this algorithm is not even competitive, it may serve as an extreme evidence to the inherent differences between the two measures. Two other algorithms studied here are the known marking algorithm, which was introduced by Fiat et al. [FKL$^{+}$] and was proved to be $2H_{k}$-competitive (against an oblivious adversary, which is the one considered in this work), and the algorithm {\em RANDOM} which was introduced by Raghavan and Snir, and was proved to be $k$-competitive. We show that although the marking algorithm has a better competitive ratio, {\em RANDOM} has a better worst-case amortized cost (at least for the two cases analyzed in this work). Two related aspects considered here are the memory size of the algorithms and the number of random bits they use.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1991
To the main CS technical reports page

Computer science department, Technion