The harmonic k-server algorithm is competitive

ABSTRACT

The k-server problem is a generalization of the paging problems, and is the most studied problem in the area of competive online problems. The Harmonic algorithm is a very natural and simple randomized algorithm for the k-server problem. We give a simple proof that the Harmonic k-server algorithm is competitive. The competitive ratio we prove is the best currently known fo the algorithm. The Harmonic algorithm is memoryless and time-efficient. This is the only such algorithm known to be competitive for the k-server problem.

REFERENCES

• 1: Yair Bartal , Adi Rosén, The distributed k-server problem—a competitive distributed translator for k-server algorithms, Journal of Algorithms, v.23 n.2, p.241-264, May. 1997 [doi>10.1006/jagm.1996.0826]
• 2: BEN-DAVID, S., BORODIN, A., KARP, R. M., TARDOS, G., AND WIGDERSON, A. 1994. On the power of randomization in online algorithms. Algorithmica 11, (1) (Jan), 2-14.
• 3: P. Berman , H. Karloff , G. Tardos, A competitive 3-server algorithm, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.280-290, January 22-24, 1990, San Francisco, California, United States
• 4: M. Chrobak , H. Karloff , T. Payne , S. Vishwanathan, New results on server problems, SIAM Journal on Discrete Mathematics, v.4 n.2, p.172-181, May 1991 [doi>10.1137/0404017]
• 5: Marek Chrobak , Lawrence L. Larmore, HARMONIC is a 3–competitive for two servers, Theoretical Computer Science, v.98 n.2, p.339-346, 18 May 1992 [doi>10.1016/0304-3975(92)90007-3]
• 6: Amos Fiat , Yuval Rabani , Yiftach Ravid, Competitive k-server algorithms, Journal of Computer and System Sciences, v.48 n.3, p.410-428, June 1994 [doi>10.1016/S0022-0000(05)80060-1]
• 7: E. F. Grove, The harmonic online K-server algorithm is competitive, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.260-266, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103448]
• 8: Elias Koutsoupias , Christos H. Papadimitriou, On the k-server conjecture, Journal of the ACM (JACM), v.42 n.5, p.971-983, Sept. 1995 [doi>10.1145/210118.210128]
• 9: Mark S. Manasse , Lyle A. McGeoch , Daniel D. Sleator, Competitive algorithms for server problems, Journal of Algorithms, v.11 n.2, p.208-230, Jun. 1990 [doi>10.1016/0196-6774(90)90003-W]
• 10: Prabhakar Raghavan , Marc Snir, Memory Versus Randomization in On-line Algorithms (Extended Abstract), Proceedings of the 16th International Colloquium on Automata, Languages and Programming, p.687-703, July 11-15, 1989
• 11: Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Performance, Theory, Verification