Main Theorem

Theorem: The trackless work function contains all information that can be useful to a trackless on-line algorithm.

That is, if A_1 is any trackless on-line algorithm for the 2-server problem on P metric spaces, then there is another trackless on-line algorithm for the same problem, A_2, such that

• After t steps, A_2 remembers nothing about the past except for the trackless work function.
• If C_1 and C_2 are the competitivenesses of A_1 and A_2, respectively, then C_2 <= C_1.