International Journal of Computer Network and Information Security (IJCNIS)
IJCNIS Vol. 4, No. 10, 8 Sep. 2012
Cover page and Table of Contents: PDF (size: 294KB)
Self Organized Replica Overlay Scheme for P2P Networks
Full Text (PDF, 294KB), PP.13-23
Views: 0 Downloads: 0
Author(s)
Shashi Bhushan
1,*
Mayank Dave
2
R. B. Patel
3
Index Terms
Data Replication, Hierarchical Quorum Consensus, Self-Organized Replica Overlay, Data Availability, Network Overhead, Fault Tolerant
Abstract
Peer-to-Peer (P2P) systems are widely used for data sharing applications in an autonomous and decentralized mode. P2P systems are suitable for large-scale distributed environments in which nodes can share resources other than data such as computing power, memory and network bandwidth. Some of important parameters that affect the performance of P2P systems are peer availability, data availability, network overhead, overlay structure, churn rate, and data access time.
In this paper a self organized replica overlay scheme "Improved Hierarchical Quorum Consensus" (IHQC) for P2P systems is proposed. This scheme organizes replicas in a Self Organized Hierarchical Logical Structure (SOHLS) that has special properties. The scheme improves performance of the system by reducing search time to form read/write quorums, reducing probability of accessing stale data, improving degree of intersection among consecutive quorums and reducing network overhead. This scheme is highly fault tolerant (tolerate up to faults) due to replication of data and inherits the best property of Read-One-Write-All (ROWA) protocol in a dynamic environment of P2P network. The architecture for IHQC is also proposed for implementing the scheme that supports improved performance of P2P systems. This scheme also maximizes the degree of intersection set of read and write quorums; hence, having higher probability to get updated data as compared to all other schemes. The mathematical correctness of the scheme is also presented in the paper. The results of simulation study of the proposed scheme also support and verify its better performance than Random and Hierarchical Quorum Scheme.
Cite This Paper
Shashi Bhushan, Mayank Dave, R. B. Patel, "Self Organized Replica Overlay Scheme for P2P Networks", International Journal of Computer Network and Information Security(IJCNIS), vol.4, no.10, pp.13-23, 2012. DOI:10.5815/ijcnis.2012.10.02
Reference
[1]D. Agrawal and A. E. Abbadi. An Efficient and Fault-Tolerant Solution for Distributed Mutual Exclusion. ACM Transactions on Computer Systems, 1991. 9(1): p. 1–20.
[2]Napster Website[ EB/ OL ] . http://www. napster.com.
[3]Gnutella Website[ EB/ OL ] . http://www.gnutella.com.
[4]T. Loukopoulos and I. Ahmad. Static and Adaptive Data Replication Algorithms for Fast Information Access in Large Distributed systems. IEEE International Conference on Distributed Computing Systems, Taipei, Taiwan, 2000. p. 385 – 392.
[5]S. Abdul-Wahid, R. Andonie, J. Lemley, J. Schwing, and J. Widger. Adaptive Distributed Database Replication Through Colonies of Pogo Ants. Parallel and Distributed Processing Symposium, IPDPS 2007. IEEE International, California USA, 2007. p. 358.
[6]J. Holliday, D. Agrawal, and A. E. Abbadi. Partial Database Replication Using Epidemic Communication. 22nd International Conference on Distributed Computing Systems, IEEE Computer Society, Vienna, Austria, 2002. p. 485–493.
[7]T. Loukopoulo and I. Ahmad. Static and Adaptive Distributed Data Replication Using Genetic Algorithms. Journal of Parallel and Distributed Computing, 2004. 64(11): p. 1270–1285.
[8]P. Francis, S. Jamin, V. Paxson, L. Zhang, D. Gryniewicz, and Y. Jin. An Architecture for a Global Internet Host Distance Estimation Service. IEEE INFOCOM '99 Conference, New York, NY, USA, 1999. p. 210-217.
[9]A. Vigneron, L. Gao, M. Golin, G. Italiano and B. Li. An Algorithm for Finding a k-median in a Directed Tree. In Information Processing Letters, 2000. 74(1, 2): p. 81-88.
[10]S. Jamin, C. Jin, T. Kurc, D. Raz and Y. Shavitt. Constrained Mirror Placement on the Internet. IEEE INFOCOM Conference, Alaska, USA, 2001. p. 1369 – 1382.
[11]I. Gashi, P. Popov, and L. Strigini. Fault Tolerance via Diversity for Off-the-Shelf Products: A Study with SQL Database Servers. IEEE Transactions on Dependable and Secure Computing, 2007. 4(4): p. 280–294.
[12]C. Wang, F. Mueller, C. Engelmann, and S. Scott. A Job Pause Service Under Lam/Mpi+Blcr for Transparent Fault Tolerance. IEEE in International Parallel and Distributed Processing Symposium, California USA, 2007. p. 1-10.
[13]Lin Wujuan, Bharadwaj Veeravalli. An Object Replication Algorithm for Real-Time Distributed Databases. Distributed Parallel Databases, MA, USA, 2006. 19: p. 125–146.
[14]Anirban Mondal, Masaru Kitsuregawa. Open Issues for Effective Dynamic Replication in Wide-Area Network Environments. Peer-to-Peer Networking and Applications, 2009. 2(3): p. 230-251.
[15]A. Bonifati, E. Chang, T. Ho, L. V. Lakshmanan, R. Pottinger and Y. Chung. Schema Mapping and Query Translation in Heterogeneous P2P XML Databases. The VLDB Journal, 2010. 19(2): p. 231-256.
[16]Ricardo JimeNez-Peris, Gustavo Alonso, Bettina Kemme, M. Patin O Martinez. Are Quorums an Alternative for Data Replication?. ACM Transactions on Database Systems, 2003. 28(3): p. 257–294.
[17]J. Kangasharju, K.W. Ross, and D. Turner. Optimal Content Replication in P2P Communities. Manuscript, 2002.
[18]Radded Al king, Abdelkader H. Franck M. Query Routing and Processing in Peer-to-Peer Data sharing Systems. International Journals of Database Management Systems (IJDMS), 2010. 2(2): p. 116-139.
[19]Jiafu Hu, Nong Xiao, Yingjie Zhao, and Wei Fu. An Asynchronous Replica Consistency Model in Data Grid. ISPA Workshops, LNCS 3759, Nanjing, China, 2005. p. 475 – 484.
[20]R.H. Thomas. A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases. ACM Transactions on Database Systems, 1979. 4(2): p. 180–209.
[21]A. Sleit, W. Al Mobaideen, S. Al-Areqi, and A. Yahya. A Dynamic Object Fragmentation and Replication Algorithm in Distributed Database Systems. American Journal of Applied Sciences, 2007. 4(8): p. 613-618.
[22]D. Agrawal, A. El. Abbadi. The Generalized Tree Quorum Protocol: An Efficient Approach for Managing Replicated Data. ACM Transactions on Database Systems, 1992. 17(4): p. 689-717.
[23]Hidehisa Takamizawa, Kazuhiro Saji. A Replica Management Protocol in a Binary Balanced Tree Structure-Based P2P Network. Journal of Computers, 2009. 4 (7): p. 631-640.
[24]Saha D, Rangarajan S, Tripathi SK. An Analysis of the Average Message Overhead in Replica Control Protocols. IEEE Transactions on Parallel Distributed Systems, 1996. 7(10): p. 1026–1034.
[25]Ahmad N, Abdalla AN, Sidek RM. Data Replication Using Read-One-Write-All Monitoring Synchronization Transaction System in Distributed Environment. Journal of Computer Science, 2010. 6(10): p. 1066–1069.
[26]P. A. Bernstein, N. Goodman. An Algorithm for Concurrency Control and Recovery in Replicated Distributed Databases. ACM Transactions on Database Systems, 1984. 9(4): p. 596–615.
[27]Jajodia, S., and Mutchler, D. Integrating Static and Dynamic Voting Protocols to Enhance File Availability. Fourth International Conference on Data Engineering (Los Angeles, Feb. 1988). IEEE, New York, 1988. p. 144-153.
[28]R. H. Thomas. A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases. ACM Transactions Database Systems, 1979. 4(2): p. 180–209.
[29]Oprea F, Reiter MK. Minimizing Response Time for Quorum-System Protocols Over Wide-Area Networks. International Conference on Dependable Systems and Networks (DSN), Edinburgh, UK, 2007. p. 409–418.
[30]Sawai Y, Shinohara M, Kanzaki A, Hara T, Nishio S. Consistency Management Among Replicas Using a Quorum System in Ad Hoc Networks. International Conference on Mobile Data Management (MDM), Nara, Japan, 2006. p. 128–132.
[31]Frain I,M'zoughi A, Bahsoun JP. How to Achieve High Throughput with Dynamic Tree-Structured Coterie. International Symposium on Parallel and Distributed Computing (ISPDC), Timisoara, Romania, 2006. p. 82–89.
[32]Osrael J, Froihofer L, Chlaupek N, Goeschka KM. Availability and Performance of the Adaptive Voting Replication. International Conference on Availability, Reliability and Security (ARES), Vienna, Austria, 2007. p. 53–60.
[33]S. Cheung, M. Ammar, and A. Ahamad. The Grid Protocol: A High Performance Scheme for Maintaining Replicated Data. IEEE Sixth International Conference on Data Engineering, Los Angeles, CA , USA, 1990. p. 438–445.
[34]Storm C, Theel O. A General Approach to Analyzing Quorum-Based Heterogeneous Dynamic Data Replication Schemes. 10th International Conference on Distributed Computing and Networking, Hyderabad, India, 2009. p. 349–361.
[35]A. Kumar. Hierarchical Quorum Consensus: A New Algorithm for Managing Replicated Data. IEEE Transactions on Computers, 1991. 40(9): p. 996-1004.
[36]Kevin Henry, Colleen Swanson, Qi Xie and Khuzaima Daudjee. Efficient Hierarchical Quorum in Unstructured Peer-to-Peer Networks. LNCS 5870, 2009. p. 183-200.
[37]Sang-Min Park, Jai-Hoon Kim, Young-Bae Ko, Won-Sik Yoon. Dynamic Data Replication Strategy Based on Internet Hierarchy BHR. Springer-Verlag Heidelberg, 2004. 3033: p. 838-846.
[38]A. Horri, R. Sepahvand, Gh. Dastghaibyfard. A Hierarchical Scheduling and replication strategy. International Journal of Computer Science and Network Security, 2008. 8: p. 30-35.
[39]Tang, M., Lee, B., Tang, X., and Yeo, C. The Impact of Data Replication on Job Scheduling Performance in the Data Grid. Future Generation Computing System, 2006. 22(3).
[40]Kavitha, R., A. Iamnitchi, and I. Foster. Improving Data Availability through Dynamic Model Driven Replication in Large Peer-to- Peer Communities. Global and Peer-to-Peer Computing on Large Scale Distributed Systems Workshop, Berlin, Germany, 2002.
[41]Ranganathan and I. Foster. Design and evaluation of Replication Strategies for a High Performance Data Grid in Computing and High Energy and Nuclear Physics. International Conference on Computing In High Energy And Nuclear Physics (CHEP'01), Beijing, China, 2001.
[42]Shashi Bhushan, R. B. Patel, M. Dave. Reducing Network Overhead with Common Junction Methodology. International Journal of Mobile Computing and Multimedia Communications, 2011. 3(3): p. 51-61.