Asymptotically Optimal Online Page Migration on Three Points

详细信息    查看全文

• 作者：Akira Matsubayashi
• 关键词：Page migration ; Work function algorithm ; Competitive analysis ; Server problem
• 刊名：Algorithmica
• 出版年：2015
• 出版时间：April 2015
• 年：2015
• 卷：71
• 期：4
• 页码：1035-1064
• 全文大小：930 KB
• 参考文献：1. Awerbuch, B., Bartal, Y., Fiat, A. (1998) Distributed paging for general networks. J.?Algorithms 28: pp. 67-104 CrossRef
  2. Awerbuch, B., Bartal, Y., Fiat, A. (2003) Competitive distributed file allocation. Inf. Comput. 185: pp. 1-40 CrossRef
  3. Bartal, Y., Fiat, A., Rabani, Y. (1995) Competitive algorithms for distributed data management. J. Comput. Syst. Sci. 51: pp. 341-358 CrossRef
  4. Bartal, Y., Charikar, M., Indyk, P. (2001) On page migration and other relaxed task systems. Theoret. Comput. Sci. 268: pp. 43-66 CrossRef
  5. Bein, W.W., Chrobak, M., Larmore, L.L. (2002) The 3-server problem in the plane. Theoret. Comput. Sci. 289: pp. 335-354 CrossRef
  6. Bienkowski, M. (2012) Migrating and replicating data in networks. Comput. Sci. Res. Dev. 27: pp. 169-179 CrossRef
  7. Bienkowski, M., Byrka, J., Korzeniowski, M., Heide, F. (2009) Optimal algorithms for page migration in dynamic networks. J.?Discrete Algorithms 7: pp. 545-569 CrossRef
  8. Black, D.L., Sleator, D.D.: Competitive algorithms for replication and migration problems. Technical Report CMU-CS-89-201, Department of Computer Science, Carnegie Mellon University (1989)
  9. Borodin, A., El-Yaniv, R. (1998) Online Computation and Competitive Analysis. Cambridge University Press, Cambridge
  10. Chrobak, M., Larmore, L.L., Reingold, N., Westbrook, J. (1997) Page migration algorithms using work functions. J.?Algorithms 24: pp. 124-157 CrossRef
  11. Karlin, A.R., Manasse, M.S., Rudolph, L., Sleator, D.D. (1988) Competitive snoopy caching. Algorithmica 3: pp. 79-119 CrossRef
  12. Koutsoupias, E., Papadimitriou, C.H. (1995) On the k-server conjecture. J.?ACM 42: pp. 971-983
  13. Lund, C., Reingold, N., Westbrook, J., Yan, D. (1999) Competitive on-line algorithms for distributed data management. SIAM J.?Comput. 28: pp. 1086-1111 CrossRef
  14. Matsubayashi, A. (2008) Uniform page migration on general networks. Int. J. Pure Appl. Math. 42: pp. 161-168
  15. Westbrook, J. (1994) Randomized algorithms for multiprocessor page migration. SIAM J.?Comput. 23: pp. 951-965 CrossRef
  
• 刊物类别：Computer Science
• 刊物主题：Algorithm Analysis and Problem Complexity
  Theory of Computation
  Mathematics of Computing
  Algorithms
  Computer Systems Organization and Communication Networks
  Data Structures, Cryptology and Information Theory
  
• 出版者：Springer New York
• ISSN：1432-0541

文摘

This paper addresses the page migration problem: given online requests from nodes on a network for accessing a page stored in a node, output online migrations of the page. Serving a request costs the distance between the request and the page, and migrating the page costs the migration distance multiplied by the page size D?. The objective is to minimize the total sum of service costs and migration costs. Black and Sleator conjectured that there exists a 3-competitive deterministic algorithm for every graph. Although the conjecture was disproved for the case D=1, whether or not an asymptotically (with respect to D) 3-competitive deterministic algorithm exists for every graph is still open. In fact, we did not know if there exists a 3-competitive deterministic algorithm for an extreme case of three nodes with D?. As the first step toward an asymptotic version of the Black and Sleator conjecture, we present 3- and (3+1/D)-competitive algorithms on three nodes with D=2 and D?, respectively, and a lower bound of 3+Ω(1/D) that is greater than 3 for every D?. In addition to the results on three nodes, we also derive ρ-competitiveness on complete graphs with edge-weights between 1 and 2?/ρ for any ρ?, extending the previous 3-competitive algorithm on uniform networks.