## 1 Introduction  
The \(k\)-server problem, introduced by [PERSON], [PERSON] and [PERSON] [1], is one of the most fundamental online problems. In this problem the input is given as \(k\) initial server positions and a sequence \(p_{1},p_{2},\cdots\) of requests in the Euclidean space, or more generally in any metric space. For each request \(p_{i}\), the online player has to select, without any knowledge of future requests, one of the \(k\) servers and move it to \(p_{i}\). The goal is to minimize the total moving distance of the servers. The \(k\)-server problem is widely considered instructive to the understanding of online problems in general, yet, there are only scattered results. The most notable open problem is perhaps the \(k\)-server conjecture, which states that the \(k\)-server problem is \(k\)-competitive. The conjecture remains open for \(k\geq 3\), despite years of effort by many researchers; it is solved for a very few special cases, and remains open even for 3 servers when the metric space has more than 6-points. The current best upper bound is \(2k-1\) given by [PERSON] and [PERSON] in 1994 [2]. The conjecture is true for \(k=2\), for the line [3], trees [4], and on fixed \(k+1\) or \(k+2\) points [5]. It is still open for the 3-server problem on more than six points and also on the circle [6]. The lower bound is \(k\) which is shown in the original paper [1]. In the randomized case, even less is known. Indeed, one of hardest problems in the area of online algorithms is to determine the exact randomized competitiveness of the \(k\)-server problem, that is, the minimum competitiveness of any randomized online algorithm for the server problem. (As is customary, we mean by \"competitive ratio\" of a randomized algorithm its expected compete ratio.) Very little is known for general \(k\). [PERSON] et al. [7] have an asymptotic lower bound, namely that the competitiveness of any randomized online algorithm for an arbitrary metric space is \(\Omega(\log k/\log^{2}\log k)\). Even the case \(k=2\) is open for the randomized \(2\)-server problem, and, despite much effort, no randomized algorithm for general metric spaces with competitiveness strictly lower than \(2\) has been found. Surprisingly, the classic algorithm random slack[8], a very simple trackless algorithm, has been the algorithm with best competitive ratio for almost two decades now. [PERSON] et al. [9] gave a lower bound of \(\frac{e}{e-1}\), which is the bound for the classical \"ski rental problem\". This bound is derived in a space with three points, where two points are located closely together and the third point is far from both of these. The best known lower bound is \(1+e^{-\frac{1}{2}}\approx 1.6065\), but this lower bound requires a space with at least four points, see [10]. (A lower bound very slightly larger than \(1+e^{-\frac{1}{2}}\) is stated in [10], but without proof.) It is indeed surprising that no randomized algorithm with competitive ratio better than 2 has been found, since it seems intuitive that randomization should help. It should be noted that generally randomization is quite powerful for online problems, since it obviously reduces the power of the adversary. Such seems to be the case for the \(2\)-server problem as well. To give intuition, consider a simple 2-server problem on the three equally spaced points \(a\), \(b\) and \(c\) on a line (See Fig. 1). It is easy to prove a lower bound of 2 for the competitive ratio of any deterministic algorithm: The adversary always gives a request on the point the server is missing. Thus for any online algorithm, \(\mathcal{A}\), its total cost is at least \(n\) - the number of requests. But it turns out by a simple case analysis that the offline cost is \(n/2\). Suppose instead that \(\mathcal{A}\) is randomized. Now if the request comes on \(b\) (with missing server), then \(\mathcal{A}\) can decide by a coin flip which server (\(a\) or \(c\)) to move.