We describe two randomized algorithms for the paging problem with k = 2, where k is the cache size. One of these algorithms uses two bookmarks and has two computational states. The other uses one bookmark and has three computational states. Each of the two algorithms is required to keep track of which of the two pages in cache is the "mru" (most recently used) page, and which is the "lru" (least recently used) page. In addition, the 2-bookmark algorithm must maintain a queue of bookmarks. The memory requirement for each of the two algorithms is thus O(1).
Each of the two algorithms is barely random, and in fact requires just one random bit. Each is 1.5-competitive against an oblivious adversary, and requires O(1) time to execute each step.
An algorithm which uses no bookmarks is called trackless. It is known that no trackless randomized algorithm for the paging problem for k = 2 can be 1.54-competitive, regardless of the availability of other resources. It is also known that no randomized online algorithm for the problem can be less than 1.5-competitive, regardless of the available resources.
With probability 0.5 the 2-bookmark algorithm behaves as the classical deterministic algorithm LRU (least recently used), which ejects the lru page whenever there is a page fault. With probability 0.5 the 2-bookmark algorithm behaves as the deterministic algorithm MRUS2, defined below.
MRUS2 (Most Recently Used if Satisfied, 2 bookmarks) has two memory states, 0 and 1. It maintains a queue Q of bookmarks. It is an invariant that Q is empty if and only if the state is 0.
Initially, the state is 0 and Q is empty. We describe the effect of a request to a page p.
This completes the description of MRUS2 and hence of the 2-bookmark algorithm.
We give three versions of the 1-bookmark algorithm. The first, the strategic version, uses a mixed strategy, as does the 2-bookmark algorithm described above. This means that, once and for all, at the beginning, it uses randomization to choose a deterministic strategy, then follows that strategy for all steps.
The 1-bookmark algorithm has three states, 0,1, and 2. There is one bookmark if the state is 1, and there is no bookmark if the state is 0 or 2.
The algorithm has two modes of behavior, which we call A and B. Initially, the algorithm chooses each mode with probability 0.5, and maintains that mode throughout all steps.
Initially, the state is 0. We describe the effect of a request to a page p.
This completes the description of the 1-bookmark algorithm.
In the behavioral version, the algorithm uses randomization at each step (if necessary) to make a decision.
The 1-bookmark algorithm has three states, 0,1, and 2. There is one bookmark if the state is 1, and there is no bookmark if the state is 0 or 2.
Initially, the state is 0. We describe the effect of a request to a page p.
This completes the description of the behavioral version of the 1-bookmark algorithm.
In the distributional version, the algorithm deterministically chooses a distribution of configurations at each step. The cost of each move is defined deterministially to be the minimum expected cost of any distribution of moves that connects consecutive distributions of configurations.
The 1-bookmark algorithm has three states, 0,1, and 2. If the state is either 0 or 2, the distribution is concentrated at one configuration where there is no bookmark. If the state is 1, there are three pages. One of these is the most recently requested page, say r, and the others we arbitrarily label q and q'. The distrubution is 0.5 on the configuration where r and q are in the cache and q' is bookmarked, and is 0.5 on the configuration where r and q' are in the cache and q is bookmarked,
Initially, the state is 0. We describe the effect of a request to a page p. Let r be the previously requested page.
This completes the description of the distributional version of the 1-bookmark algorithm.
