On List Update and Work Function Algorithms(8)

Abstract. The list update problem, a well-studied problem in dynamic data structures, can be described abstractly as a metrical task system. In this paper, we prove that a generic metrical task system algorithm, called the work function algorithm, has cons

8

3 A di erent view on list factoringA technique which has been used in the past to analyze list update algorithms is the list factoring technique, which reduces the competitive analysis of list accessing algorithms to lists of size two 3], 7], 18], 4], 19]. For example, this technique, in conjunction with phase partitioning, was used to prove that an algorithm called TimeStamp is 2-competitive 4], 19]. In this section, we repeat the development of this technique, but present it in a somewhat di erent way, in terms of a partial order on elements in the list.6 This view leads us to a simple generalization of previous results and will assist us in our study of WFA0 . Consider the metrical task system corresponding to a list of length two. In this case there are two lists, (a; b) (a in front of b) and (b; a) (b in front of a), and the distance between these two states is 1. Since for all t we have !t ((a; b))? 1 !t ((b; a)) !t((a; b))+1; we can characterize the work functions at any given time t as having one of three distinct properties: !t ((a; b))< !t ((b; a)), which we denote a b, !t ((a; b))= !t ((b; a)), which we denote a b, or !t ((a; b))> !t ((b; a)), which we denote a b. It is easy to verify directly from Equation (1) the transitions between these three properties as a result of references in the string .

a

-

?a b b

a a b

? 6b

a a b

b

6

Fig. 1. The three-state DFA: the state a

b corresponds to the case !t ((a; b))= !t ((b; a))? 1, the state a b corresponds to the case !t ((a; b))= !t ((b; a)), and the state a b corresponds to the case !t ((a; b))= !t ((b; a))+ 1The resulting three-state DFA shown in Figure 1 can be used to completely characterize the work functions, the optimal o ine list con guration, and the optimal cost to service a request sequence . The start state of the DFA is determined by the initial order of the elements in the list: it is a b if the for any states s that serve the t+ 1st request, !t+1 (s)= !t (s). Hence WFA and WFA de ne the same algorithm, and so WFA is 2k? 1 competitive for the k-server problem. The proof that WFA is 2n? 1 competitive for any metrical task system with n states also holds for WFA (using the same potential function), and so WFA also is 2n? 1 competitive for any metrical task system.0 0 0 0

6 This partial order has apparently been considered by Albers, von Stengel and

Werchner in the context of randomized list update, and was used as a basis for an optimal randomized online algorithm for lists of length 4. 20]