In the k-server problem, we are given a complete graph on
n vertices, an arbitrary distance function, and k servers
on k nodes. Then requests on vertices arrive over time and
we have to fulfil them by moving a server on the requested
vertex so that the total distance travelled by the tokens
is minimised. We will focus on the Harmonic Algorithm,
which moves servers with probability inversely proportional
to its distance to the request. It is a very natural algorithm,
however, the currently known gap in its competitive ratio
is huge: from quadratic to exponential in k.
We will discuss about a particular case where the lower
bound is known to be tight. We will also show some properties
of weighted random walks, which naturally appear in the
analysis, and relate these to electrical circuits. Finally,
we will introduce a conjecture on two small problems, which
can yield a polynomial upper bound on the general instance.