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.