297Accesses
Abstract
The replication of popular data objects can effectively reduce the access time and bandwidth requirements of network services. We study the replication problem in the model of distributed replication groups and propose two distributed algorithms: an approximation optimal replication algorithm, which is an asynchronous distributed algorithm as it takes more time to be completed. However its performance approaches the optimal algorithm, and a fast replication algorithm that is very suitable as the initial algorithm of the approximation optimal algorithm. We give a proof of the complexity of the algorithms, and show that the time and communication complexities of the algorithms are polynomial with respect to the number of objects and the maximum storage capacities of the servers. Finally, simulation experiments are performed to investigate the performance of the algorithms, and the results show that the two algorithms can effectively solve the replication problem.
This is a preview of subscription content,log in via an institution to check access.
Access this article
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
Price includes VAT (Japan)
Instant access to the full article PDF.






Similar content being viewed by others
References
Leff, A., Wolf, J.L., Yu, P.S.: Replication algorithms in a remote caching architecture. IEEE Trans. Parallel Distrib. Syst.4(11), 1185–1204 (1993)
Zaman, S., Grosu, D.: A distributed algorithm for the replica placement problem. IEEE Trans. Parallel Distrib. Syst.22(9), 1455–1468 (2011)
Laoutaris, N., Telelis, O., Zissimopoulos, V., Stavrakakis, I.: Distributed selfish replication. IEEE Trans. Parallel Distrib. Syst.17(12), 1401–1413 (2006)
Khan, S.U., Ahmad, I.: Comparison and analysis of ten static heuristics-based Internet data replication techniques. J Parallel Distrib. Comput.68(2), 113–136 (2008)
He, D., Liang, Y., Hang, Z.: Replicate distribution method of minimum cost in cloud storage for Internet of things. In: Proceedings IEEE symposium network computing and information security (NCIS), pp. 89–92 (2011)
Krishnan, P., Raz, D., Shavitt, Y.: The cache location problem. IEEE/ACM Trans. Netw.8(5), 568–582 (2000)
Tang, B., Gupta, H., Das, S.R.: Benefit-based data caching in ad hoc networks. IEEE Trans. Mob. Comput.7(3), 289–304 (2008)
Kangasharju, J., Roberts, J., Ross, K.W.: Object replication strategies in content distribution networks. Comput. Commun.25(4), 376–383 (2002)
Baev, I., Rajaraman, R., Swamy, C.: Approximation algorithms for data placement problems. SIAM J. Comput.38(4), 1411–1429 (2008)
Li, B., Golin, M.J., Italiano, G.F., Deng, X., Sohraby, K.: On the optimal placement of web proxies in the Internet. In: Proceedings of conference computer communication (IEEE INFOCOM) (1999)
Changjie, G., Zhe, X., Yuzhuo, Z.: A novel greedy heuristic placement algorithm in distributed cooperative proxy systems. Proc. IEEE Symp. Info-Tech Info-Net2001(5), 229–234 (2001)
Kalpakis, K., Dasgupta, K., Wolfson, O.: Optimal placement of replicas in trees with read, write, and storage costs. IEEE Trans. Parallel Distrib. Syst.12(6), 628–637 (2001)
Fadelelmoula, A.A., Dominic, P.D.D.: Optimistic replication in mobile traffic control environment. Intelligent and Advanced Systems (ICIAS 2007), pp. 543–548 (2007)
Keqiu, L., Hong, S., Chin, F.Y.L., Weishi, Z.: Multimedia object placement for transparent data replication. IEEE Trans. Parallel Distrib. Syst.18(2), 212–224 (2007)
Zhou, J., Wang, Y., Li, S.: An optimistic replication algorithm to improve consistency for massive data. Lecture Notes in Computer Science, pp. 713–718 (2005)
Loukopoulos, T., Ahmad, I.: Static and adaptive data replication algorithms for fast information access in large distributed systems. Proc. IEEE Symp. Distrib. Comput. Syst.2000, 385–392 (2000)
Loukopoulos, T., Ahmad, I.: Static and adaptive distributed data replication using genetic algorithms. J. Parallel Distrib. Comput.64(11), 1270–1285 (2004)
Xin, S., Jun, Z., Qiongxin, L., Yushu, L.: Dynamic data replication based on access cost in distributed systems. In: Proceedings of IEEE symposium computer sciences and convergence information technology (ICCIT ’09), pp. 829–834 (2009)
Triantafillou, P., Taylor, D.J.: Multiclass replicated data management: exploiting replication to improve efficiency. IEEE Trans. Parallel Distrib. Syst.5(2), 121–138 (1994)
Yi-Hsuan, F., Nen-Fu, H., Yen-Min, W.: Efficient and adaptive stateful replication for stream processing engines in high-availability cluster. IEEE Trans. Parallel Distrib. Syst.22(11), 1788–1796 (2011)
Zhang, W.: Replication cache: a small fully associative cache to improve data cache reliability. IEEE Trans. Comput.54(12), 1547–1555 (2005)
Xueyan, T., Chanson, S.T.: Minimal cost replication of dynamic Web contents under flat update delivery. IEEE Trans. Parallel Distrib. Syst.15(5), 431–439 (2004)
Shen, K., Yang, T., Chu, L.: Clustering support and replication management for scalable network services. IEEE Trans. Parallel Distrib. Syst.14(11), 1168–1179 (2003)
Shi, Z., Beard, C., Mitchell, K.: Analytical models for understanding misbehavior and MAC friendliness in CSMA networks. Perform. Eval.66(9–10), 469–487 (2009)
Shi, Z., Beard, C., Mitchell, K.: Analytical models for understanding space, backoff and flow correlation in CSMA wireless networks. Wirel. Netw.19, 393–409 (2013)
Shi, Z., Beard, C., Mitchell, K.: Competition, cooperation, and optimization in multi-hop CSMA networks with correlated traffic. Int. J. Next-Gener. Comput.3(3), 117–120 (2012)
Shi, Z.: Stochastic modeling, correlation, competition, and cooperation in a CSMA wireless network. ProQuest, UMI Dissertation Publishing (2011)
Shi, Z., Gu, R.: Efficient implementation of particle swarm optimization algorithm. Int. J. Soft Comput. Math. Control.2(4), 1–13 (2013)
Shi, Z., Gu, R.: A framework for mobile cloud computing selective service system. IEEE 2013 Wireless Telecommunications Symposium, pp. 1–5 (2013)
Shi, Z., Beard, C.: QoS in the mobile cloud computing environment, mobile computing over cloud: technologies, services, and applications (2013)
Acknowledgments
This work was supported by Key Program of National Natural Science Foundation of P.R. China under Grant No.61233003 and China Postdoctoral Science Foundation under Grant No. 2014M561839.
Author information
Authors and Affiliations
Department of Automation, University of Science and Technology of China, Hefei, 230021, China
Xiaofeng Jiang, Jun Li & Hongsheng Xi
- Xiaofeng Jiang
You can also search for this author inPubMed Google Scholar
- Jun Li
You can also search for this author inPubMed Google Scholar
- Hongsheng Xi
You can also search for this author inPubMed Google Scholar
Corresponding author
Correspondence toXiaofeng Jiang.
Rights and permissions
About this article
Cite this article
Jiang, X., Li, J. & Xi, H. Distributed Algorithms for a Replication Problem of Popular Network Data.J Netw Syst Manage24, 34–56 (2016). https://doi.org/10.1007/s10922-014-9338-0
Received:
Revised:
Accepted:
Published:
Issue Date:
Share this article
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative