Computer Science
Computer Science
bullet Gourds will fly: Rowan University American Society of Mechanical Engineers to host fifth annual Pumpkin Chunkin’ | More

bullet Hail to the Profs! Homecoming 2014 in pictures | More

bullet Second biennial ScholarFest to celebrate Rowan research | More

bullet Rowan hosts talk on “Controlling Ebola Virus Outbreaks: A New Strategy to Block Virus Transmission and Spread” | More

bullet Prof pride: Alumni flock to campus for Homecoming | More

Technical Report Number TR1995-3

Title
On Space Bounded Server Algorithms

Authors
Ganesh Baliga
Department of Computer Science
Rowan College of New Jersey
Glassboro, NJ 08028


Steven Hughes
Department of Computer Science
Indiana University
Bloomington, IN


Anil M. Shende
Dept. of Mathematics, Computer Science & Physics
Roanoke College
Salem, VA 24153

Abstract

This paper studies space bounded algorithms, i.e., algorithms that use
a constant amount of scratch space, for the k-server problem. The
paper first shows a characterization of the set of space bounded
algorithms that are competitive in finite metric spaces. The result
yields a method for (1) effectively deciding if a given space bounded
algorithm is competitive in a given finite metric space, and (2) for
designing competitive space bounded algorithms in finite metric
spaces.

The above results are then refined, in particular using the geometry
of metric spaces, to develop two methods for obtaining an upper bound
on competitive factors of arbitrary space bounded algorithms. One of
these methods is then used to show that any algorithm, employing the
Least Recently Used strategy, is linearly competitive on a uniform
metric space.