A Fast Replica Placement Methodology for Large-scale Distributed Computing Systems

Fine-grained data replication over the Internet allows duplication of frequently accessed data objects, as opposed to entire sites, to certain locations so as to improve the performance of largescale content distribution systems. In a distributed system, agents representing their sites try to maximize their own benefit since they are driven by different goals such as to minimize their communication costs, latency, etc. In this paper, we will use game theoretical techniques and in particular auctions to identify a bidding mechanism that encapsulates the selfishness of the agents, while having a controlling hand over them. In essence, the proposed game theory based mechanism is the study of what happens when independent agents act selfishly and how to control them to maximize the overall performance. A bidding mechanism asks how one can design systems so that agents- selfish behavior results in the desired system-wide goals. Experimental results reveal that this mechanism provides excellent solution quality, while maintaining fast execution time. The comparisons are recorded against some well known techniques such as greedy, branch and bound, game theoretical auctions and genetic algorithms.

• Samee Ullah Khan
• C. Ardil

• Data replication
• auctions
• static allocation
• pricing.

[1] M. Arlitt and T. Jin, "Workload characterization of the 1998 World Cup
Web Site," Technical Report, Hewlett Packard Lab, Palo Alto, HPL-
1999-35(R.1), 1999.
[2] K. Calvert, M. Doar, E. Zegura, "Modeling Internet Topology," IEEE
Communications, 35(6), pp. 160-163, 1997.
[3] D. Grosu and A. Chronopoulos, "Algorithmic Mechnism Design for
Load Balancing in Distributed Systems," IEEE Trans. Systems, Man and
Cybernatics B, 34(1), pp. 77-84, 2004.
[4] S. Jamin, C. Jin, Y. Jin, D. Riaz, Y. Shavitt and L. Zhang, "On the
Placement of Internet Instrumentation," in IEEE INFOCOM, 2000.
[5] S. Khan and I. Ahmad, "Heuristic-based Replication Schemas for Fast
Information Retrevial over the Internet," in 17th International
Conference on Parallel and Distributed Computing Systems, San
Francisco, U.S.A., 2004.
[6] S. Khan and I. Ahmad, "A Game Theoretical Solution for Web Content
Replication," Technical Report, CSE-UTA, 2004.
[7] S. Khan and I. Ahmad, "A Pure Nash Equilibrium-based Game
Theoretical Method for Data Replication across Multiple Servers," IEEE
Transactions on Knowledge and Data Engineering, accepted to appear in
2009.
[8] B. Li, M. Golin, G. Italiano and X. Deng, "On the Optimal Placement of
Web Proxies in the Internet," in IEEE INFOCOM, 2000.
[9] T. Loukopoulos, and I. Ahmad, "Static and Adaptive Distributed Data
Replication using Genetic Algorithms," Journal of Parallel and
Distributed Computing, 64(11), pp. 1270-1285, 2005.
[10] T. Loukopoulos, I. Ahmad, and D. Papadias, "An Overview of Data
Replication on the Internet," in IEEE International Symposium on
Parallel Processing and Networking, pp. 31-36, 2002.
[11] N. Nisan and A. Ronen, "Algorithimic Mechanism Design," in 31st
ACM Symposium on Theory of Computing, pp. 129-140, 1999.
[12] L. Qiu, V. Padmanabhan and G. Voelker, "On the Placement of Web
Server Replicas," in IEEE INFOCOM, 2001.
[13] S. Rhea, C. Wells, P. Eaton, D. Geels, B. Zhao, H. Weatherspoon, J.
Kubiatowicz, "Maintenance-free Global Storage," IEEE Internet
Computing, 5(5), pp. 40-49, 2001.
[14] W. Vickrey, "Counterspeculation, Auctions and Competitive Sealed
Tenders," Journal of Finance, pp. 8-37, 1961.