Wednesday, January 23, 2002

We will start by introducing the paging problem, introduced in Chapter 3
(page 32) of the textbook.  The paging problem is one of the simplest
online problems, yet also one of the most important.  There are substantial
open questions about the paging problem, and we will spend a considerable
portion of the semester discussing it.

Using the paging problem as an example, I will explain the meaning of
some of the more important concepts of this area, including
"online algorithm," "randomized alogirithm," and "competitiveness."

The paging problem is quite simple to state.  A computer has two kinds
of memory, "cache" and "slow."  The data of the computer consist of
"pages."  The cache can hold k pages, where k is a given (small) number.
The slow memory can hold many more pages; usually, we place no limit
on the number.

The computer can only read and write pages if they are in cache, so that
if the program needs data which are on a given page, that page must be
copied into the cache.  If many pages are needed during the running of
the program, the computer must sometimes "eject" a page, meaning that a
page in the cache is copied back to slow memory, in order to make room
in the cache for some other page.  Copying pages takes time, and the goal
is to minimize the number of times a page is copied to cache.

The inputs for the paging problem are "requests."  Each request is for
a particular page to be present in the cache.  If that page is already
in the cache, that is called a "hit," which is good.  If that page is
not in the cache, that is called a "fault," which imples that the page
must be copied into the cache, at some cost.  We usually take that cost
to be 1.  At the same time, the algorithm must eject one of the cache
pages, to make room for the requested page.  All a paging algorithm does
is choose which page to eject.

A "step" consists of a request, followed by an ejection if necessary.
We say that the cost of the step is 1 if there is an ejection, 0 otherwise.

The "request sequence" is the sequence of page requests, through time.
For example, if the pages are represented by the letters from a to z,
"abcadabefa" is an example of a request sequence.  For a given initial
cache (we always assume that the cache is full at the beginning) and
a given request sequence, there is a simple dynamic programming algorithm
which computes the optimal "service sequence," meaning, the sequence
consisting of which page to eject at each step.  This dynamic programming
algorithm is "offline," meaning that it depends on knowing the entire
request sequence.  The cost of that service sequence we call the
"optimal cost."

We say that a paging algorithm is "online" if it must make a choice of
which page to eject at a given step without knowledge of future requests.
Can an online paging algorithm guarantee optimal cost?  This is not a
trivial question, and in fact, is the central question of the subject
of online algorithms.  The answer is "no"; but then, since no online
algorithm can be "optimal," how can we say that one online algorithm is
"better" than another?  I will throw this question open for class
discussion today.
