\begin{thebibliography}{1} \bibitem{BaChLa98} Yair Bartal, Marek Chrobak, and Lawrence~L. Larmore. \newblock A randomized algorithm for two servers on the line. \newblock In {\em Proc. 6th European Symp. on Algorithms (ESA)}, Lecture Notes in Comput. Sci., pages 247--258. Springer, 1998. \bibitem{BorElY98} Allan Borodin and Ran El-Yaniv. \newblock {\em Online Computation and Competitive Analysis}. \newblock Cambridge University Press, 1998. \bibitem{ChKaPV91} Marek Chrobak, Howard Karloff, Tom~H. Payne, and Sundar Vishwanathan. \newblock New results on server problems. \newblock {\em SIAM J. Discrete Math.}, 4:172--181, 1991. \bibitem{ChrLar91A} Marek Chrobak and Lawrence~L. Larmore. \newblock An optimal online algorithm for $k$ servers on trees. \newblock {\em SIAM J. Comput.}, 20:144--148, 1991. \bibitem{ChLaLR97} Marek Chrobak, Lawrence~L. Larmore, Carsten Lund, and Nick Reingold. \newblock A better lower bound on the competitive ratio of the randomized 2-server problem. \newblock {\em Inform. Process. Lett.}, 63:79--83, 1997. \bibitem{KouPap94B} Elias Koutsoupias and Christos Papadimitriou. \newblock Beyond competitive analysis. \newblock In {\em Proc. 35th Symp. Foundations of Computer Science (FOCS)}, pages 394--400. IEEE, 1994. \bibitem{KouPap95A} Elias Koutsoupias and Christos Papadimitriou. \newblock On the $k$-server conjecture. \newblock {\em J. ACM}, 42:971--983, 1995. \bibitem{LunRei94} Carsten Lund and Nick Reingold. \newblock Linear programs for randomized on-line algorithms. \newblock In {\em Proc. 5th Symp. on Discrete Algorithms (SODA)}, pages 382--391. ACM/SIAM, 1994. \bibitem{MaMcSl90} Mark Manasse, Lyle~A. McGeoch, and Daniel Sleator. \newblock Competitive algorithms for server problems. \newblock {\em J. Algorithms}, 11:208--230, 1990. \end{thebibliography}