Replicating Data Objects in Large-scale Distributed Computing Systems using Extended Vickrey Auction

Authors: Samee Ullah Khan, Ishfaq Ahmad

Abstract:

This paper proposes a novel game theoretical technique to address the problem of data object replication in largescale distributed computing systems. The proposed technique draws inspiration from computational economic theory and employs the extended Vickrey auction. Specifically, players in a non-cooperative environment compete for server-side scarce memory space to replicate data objects so as to minimize the total network object transfer cost, while maintaining object concurrency. Optimization of such a cost in turn leads to load balancing, fault-tolerance and reduced user access time. The method is experimentally evaluated against four well-known techniques from the literature: branch and bound, greedy, bin-packing and genetic algorithms. The experimental results reveal that the proposed approach outperforms the four techniques in both the execution time and solution quality.

Keywords: Auctions, data replication, pricing, static allocation.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1334465

References:

[1] T. Loukopoulos, and I. Ahmad, "Static and adaptive distributed data replication using genetic algorithms," J. of Parallel and Distributed Comput., vol. 64, no. 11, pp. 1270-1285, 2004.
[2] B. Awerbuch, Y. Bartal and A. Fiat, "Competitive distributed file allocation," in Proc. of 25th ACM Symp. on Theory Of Comput., Victoria, B.C., Canada, 1993, pp. 164-173.
[3] T. Abdelzaher and N. Bhatti, "Web content adaptation to improve sever workload behavior," Comput. Networks, vol. 21, no. 11, pp. 1536-1577, 1999.
[4] A. Heddaya and S. Mirdad, "WebWave: Globally load balanced fully distributed caching of hot published documents," in Proc. 17th Intl. Conf. on Distributed Comput. Systems, Baltimore, Maryland, 1997, pp. 160-168.
[5] J. Kangasharju, J. Roberts and K. Ross, "Object replication strategies in content distribution networks," in Proc. of Workshop on Content Caching and Distribution, 2001, pp. 455-466.
[6] S. Khan and I. Ahmad, "Heuristic-based replication schemas for fast information retrieval over the internet," in Proc. of 17th Intl. Conf. on Parallel and Distributed Comput. Systems, 2004, pp. 278-283.
[7] S. Mahmoud and J. Riordon, "Optimal allocation of resources in distributed information networks," ACM Trans. on Database Systems, vol. 1, no. 1, pp. 66-78, 1976.
[8] T. Loukopoulos, D. Papadias, and I. Ahmad, "An overview of data replication on the internet," in Proc. of IEEE Intl. Symp. on Parallel Architectures, Algorithms and Networks, 2002, pp. 31-36.
[9] W. Vickrey, "Counterspeculations, auctions and competitive sealed-bid tenders," J. of Finance, vol. 16, pp. 15-27, 1961.
[10] L. Qiu, V. Padmanabhan and G. Voelker, "On the placement of web server replicas," in Proc. of the IEEE INFOCOM, 2001, pp. 1587-1596.
[11] W. Chu, "Optimal file allocation in a multiple computer system," IEEE Trans. on Computers, vol. 18, no. 10, pp. 885-889, 1969.
[12] R. Casey, "Allocation of copies of a file in an information network," in Proc. Spring Joint Computer Conf., IFIPS, 1972, pp. 617-625.
[13] K. Eswaran, "Placement of records in a file and file Allocation in a computer network," in Proc. of Intl. Information Processing Conf., 1974, pp. 304-307.
[14] L. Dowdy and D. Foster, "Comparative models of the file assignment problem," ACM Computing Surveys, vol. 14, no. 2, pp. 287-313, 1982.
[15] K. Chandy and J. Hewes, "File allocation in distributed systems," in Proc. of the International Symp. on Comput. Performance Modeling, Measurement and Evaluation, 1976, pp. 10-13.
[16] S. Hakimi, "Optimum location of switching centers and the absolute centers and medians of a graph," Operations Research, vol. 12, pp. 450- 459, 1964.
[17] S. Jamin, C. Jin, Y. Jin, D. Riaz, Y. Shavitt and L. Zhang, "On the placement of internet instrumentation," in Proc. of the IEEE INFOCOM, 2000, pp. 295-304.
[18] M. Karlsson and M. Mahalingam, "Do we need replica placement algorithms in content delivery networks?" in Proc. of Web Caching and Content Distribution Workshop, 2002, pp. 117-128.
[19] S. Cook, J. Pachl, and I. Pressman, "The optimal location of replicas in a network using a READ-ONE-WRITE-ALL policy," Distributed Computing, vol. 15, no. 1, pp. 57-66, 2002.
[20] S. Khan and I. Ahmad, "A powerful direct mechanism for optimal www content replication," in Proc. of 19th IEEE International Parallel and Distributed Processing Symposium, 2005, p. 86.
[21] S. Jamin, C. Jin, T. Kurc, D. Raz and Y. Shavitt, "Constrained mirror placement on the internet," in Proc. of the IEEE INFOCOM, 2001, pp. 31-40.
[22] B. Li, M. Golin, G. Italiano and X. Deng, "On the optimal placement of web proxies in the internet," in Proc. of the IEEE INFOCOM, 2000, pp. 1282-1290.
[23] K. Kalpakis, K. Dasgupta, and O. Wolfson, "Optimal placement of replicas in trees with read, write, and storage Costs," IEEE Trans. on Parallel and Distributed Systems, vol. 12, no. 6, pp. 628-637, 2001.
[24] I. Cidon, S. Kutten, and R. Soffer, "Optimal allocation of electronic content," in Proc. of IEEE INFOCOM, 2001, pp. 1773-1780.
[25] P. Krishnan, D. Raz, and Y. Shavitt, "The Cache Location Problem," IEEE/ACM Trans. on Networking, 8(5), pp. 568-582, 2000.
[26] P. Radoslavov, R. Govindan, and D. Estrin, "Topology-informed internet replica placement," Computer Communications, vol. 25, no. 4, pp. 384-392, 2002.
[27] A. Venkataramanj, P. Weidmann, and M. Dahlin, "Bandwidth constrained placement in a WAN," in Proc. ACM Symp. on Principles of Distributed Computing, 2001, pp. 134-143.
[28] M. Korupolu and C. Plaxton, "Analysis of a local search heuristic for facility location problems," J. of Algorithms, vol. 37, no. 1, pp. 146- 188, 2000.
[29] C. Krick, H. Racke, and M. Westermann, "Approximation algorithms for data management in networks," in Proc. of the Symp. on Parallel Algorithms and Architecture, 2001, pp. 237-246.
[30] B.-G. Chun, K. Chaudhuri, H. Wee, M. Barreno, C. Papadimitriou and J. Kubiatowicz, "Selfish caching in distributed systems: A gametheoretic analysis," in Proc. of 23rd ACM Symp. on Principles of Distributed Computing, 2004, pp. 21-30.
[31] N. Laoutaris, O. Telelis, V. Zissimopoulos and I. Stavrakakis, "Local utility aware content replication," in IFIP Networking Conference, 2005, pp. 455-468.
[32] B. Narebdran, S. Rangarajan and S. Yajnik, "Data distribution algorithms for load balancing fault-tolerant web access," in Proc. of the 16th Symp. on Reliable Distributed Systems, 1997, pp. 97-106.
[33] M. Rabinovich, "Issues in web content replication," Data Engineering Bulletin, vol. 21, no. 4, pp. 21-29, 1998.
[34] M. Arlitt and T. Jin, "Workload characterization of the 1998 World Cup Web Site," tech. report, HP Lab, Palo Alto, HPL-1999-35(R.1), 1999.
[35] K. Calvert, M. Doar, E. Zegura, "Modeling Internet topology," IEEE Communications, 35(6), pp. 160-163, 1997.
[36] P. Apers, "Data Allocation in Distributed Database Systems," ACM Trans. Database Systems, 13(3), pp. 263-304, 1988.