Wolfgang Bein University of Nevada, Las Vegas Department of Computer Science
Various models of computation involve restrictions on the power of an algorithm. ``On-line" itself, in fact, is such a restriction. "Bounded memory" is a further restriction which is frequently considered.
A novel concept ``tracklessness" is introduced for the 
server
problem. Tracklessness is a property of an online
algorithm which is a restriction on what input data the
algorithm uses in its computation, and on what outputs the
algorithm gives. Specifically, for each request point,
the algorithm is only given as input the distances of
the current server positions to the request point. A trackless
algorithm may memorize such distance values, but is restricted
from storing explicitly any points of the metric space.
In the algorithm's response to a request, the algorithm is
limited to producing output that identifies which server
moves, and does not mention points in the metric space
explicitly. Many known algorithms are trackless
(e.g. BALANCE, BALANCE_SLACK, RANDOM_SLACK, and HARMONIC) whereas
the Workfuntion Algorithm is not trackless.
The -server conjecture fails for trackless
algorithms. A lower bound of 
on the
competitiveness of any deterministic trackless 
-server algorithm
and a lower bound of 
on the competitiveness
of any randomized trackless -server problem are given.
We then discuss the concept of tracklessness as it applies to
paging. Reducing the paging problem to the server problem
in a uniform space, the tracklessness restriction
translates into the rule that no bookmarks are used.
An efficient randomized online algorithm for the paging problem
for cache size 2 is given, which is 
-competitive
against an oblivious adversary. The algorithm is almost trackless
as it keeps track of at most one page in slow memory at any time.
A lower bound of
is given for
the competitiveness of any trackless online algorithm
for the same problem, i.e., an algorithm that keeps track of
no page outside the cache.
