On List Update and Work Function Algorithms(6)

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

6

2.2 Elementary identities Proposition 1.!t (s) !t (s0 )+ d(s; s0 ):Proof. For notational convenience, we show !t+1 (s) !t+1 (s0 )+ d(s; s0 ). From the de nition (Equation 1), there is some s for which !t+1 (s0 )= !t (~)+ (~)+~ s s d(~; s0 ). We know that !t (~)+ (~)+ d(~; s) is an upper bound on !t+1 (s) (by s s s s Equation 1). By the triangle inequality, d(~; s) d(~; s0 )+ d(s0; s). So we have s s !t+1 (s) !t+1 (s0 )+ d(s; s0 ). t u

Proposition 2.!t+1 (s) !t(s):Proof. By the alternative de nition above (Equation 1), for some s0 we have !t+1 (s)= !(s0 )+ d(s; s0 )+ (s0 ). By Proposition 1, !t (s) !(s0 )+ d(s; s0 ). Since all task costs are nonnegative, (s0 ) 0, and the result follows. t u

Proposition 3.!t+1 (s) !t (s)+ (s):Proof. By the de nition (Equation 1), !t+1 (s)= mins (!t (s0 )+ (s0 )+ d(s; s0 )), so for all such s0, !t+1 (s) !t (s0 )+ (s0 )+ d(s; s0 ). Substituting s for s0, and noting that d(s; s)= 0, the result follows. t u0

Proposition 4. For any s,!t+1 (s)= !t+1 (f )+ d(f; s)for some state f that is fundamental at time t. (The state s is derived from some fundamental state.) Proof. By the de nition (Equation 1), there is some f for which !t+1 (s)= !t (f )+ (f )+ d(f; s). We want to show that this f is fundamental. By Proposition 1, !t+1 (s) !t+1 (f )+ d(f; s); so !t (f )+ (f ) !t+1 (f ). But !t (f )+ (f ) !t+1 (f ) by Proposition 3. Hence !t(f )+ (f )= !t+1 (f ) and f is fundamental at time t. Then !t+1 (s)= !t+1

(f )+ d(f; s) by substitution. t u at time t, and suppose further that !t+1(s)= !t+1 (f )+ d(f; s) where f is fundamental. (There is at least one such state f by Proposition 4.) Then f is also wfa-eligible at time t, and x(f )= x(s). (The fundamental state f is wfa-eligible if s is.)

Proposition 5. Suppose WFA0 is in state st at time t. Suppose s is wfa-eligible