Wed Jan 23 17:44:37 PST 2008

Dear Jiri,

I am sending you the pdf file of something I wrote in 2006.

Section 1 is supposed to define what a trackless work function is.
I left that out.  Sorry ... I'll try to fill you in tomorrow.  The
domain of a trackless work function is the set of all equivalence classes
of configurations, where two configurations are equivalent if we cannot
distinguish them.

Calligraphic M_3 is the class of all metric spaces which integral
distances in the range 1..3.

The individual figure in Figure 1 are trackless work functions
in the class M_3.  Despite the fact that M_3 contains infinite
spaces, there are only finitely many possible trackless work functions
for that class.  The red dots are the positions of "out" servers.
The black dot is the most recent request point.  If the figure is
surrounded by a black outline, we have moved a server to the request.
If the figure is surrounded by a red outline, the adversary has made
a request and we have not yet served that request.  In both cases,
the numbers in each box is the value of the work function on
the pair consisting of the black dot and that box.

The number in the small green box is the potential of that configuration,
given that the competitiveness is 3.  A black arrow is an adversary
move, and a red arrow is our move.  The red number is our cost.  The
black number is the amortized adversary cost.

Figure 2 shows a much less abstract lower bound proof.  In this case
the metric space is a hypercube of dimension 3.  Notation is similar to
that of Figure 1.
