A Hybrid P2P Storage Scheme Based on Erasure Coding and Replication

Authors: Usman Mahmood, Khawaja M. U. Suleman

Abstract:

A peer-to-peer storage system has challenges like; peer availability, data protection, churn rate. To address these challenges different redundancy, replacement and repair schemes are used. This paper presents a hybrid scheme of redundancy using replication and erasure coding. We calculate and compare the storage, access, and maintenance costs of our proposed scheme with existing redundancy schemes. For realistic behaviour of peers a trace of live peer-to-peer system is used. The effect of different replication, and repair schemes are also shown. The proposed hybrid scheme performs better than existing double coding hybrid scheme in all metrics and have an improved maintenance cost than hierarchical codes.

Keywords: Erasure Coding, P2P, Redundancy, Replication.

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

References:

[1] A. Dimakis, P. Godfrey, M. Wainwright, AND K. Ramchandran: The benefits of network coding for peer-to-peer storage systems. In Workshop on Network Coding, Theory, and Applications, 2007.
[2] J. Araujo, F. Girore, and J. Monteiro: Hybrid Approaches for Distributed Storage. Proceedings of the 4th international conference on Data management in grid and peer-to-peer systems, 2011.
[3] R. Bhagwan, D. Moore, S. Savage, G. Voelker: Replication strategies for highly available peer-to-peer storage. Future Directions in Distributed Computing (FuDiCO), 2002.
[4] C. Blake, R. Rodrigues: High availability, scalable storage, dynamic peer networks: pick two. Proceedings of the 9th Workshop on Hot Topics in Operating Systems (HotOS-IX), Lihue, Hawaii, 2003.
[5] H. Weatherspoon and J. Kubiatowicz: Erasure coding vs. replication: A quantitative comparison. Proceedings of the 1st International Workshop on Peer-to-Peer Systems (IPTPS 2002), March 2002.
[6] R. Rodrigues, B. Liskov: High Availability in DHTs: Erasure Coding vs. Replication. 4th International Workshop on Peer-to-Peer Systems (IPTPS'05). Ithaca, New York, USA. February 2005.
[7] A. Duminuco and E. Biersack, “Hierarchical codes: How to make erasure codes attractive for peer-to-peer storage systems,” in IEEE P2P, 2008.
[8] A. Adya, W. Bolosky, M. Castro, G. Cermak, R. Chaiken, J. Douceur, J. Howell, J. Lorch, M. Theimer, R. Wattenhofer: FARSITE: federated, available, and reliable storage for an incompletely trusted environment. 5th Symposium on Operating Systems Design and Implementation (OSDI), 2002.
[9] P. Druschel and A. Rowstron. PAST: A large-scale, persistent peer-to-peer storage utility. In USENIX Workshop on Hot Topics in Operating Systems (HotOS), 2001.
[10] F. Dabek, M. F. Kaashoek, D. Karger, R. Morris, and I. Stoica. Wide-area cooperative Storage with cfs. In ACM Symposium on Operating Systems Principles (SOSP), 2001.
[11] A. Haeberlen, A. Mislove, and P. Druschel. Glacier: highly durable, decentralized storage despite massive correlated failures. In USENIX Symposium on Networked Systems Design and Implementation (NSDI), 2005.
[12] Williams, C., Huibonhoa, P., Holliday, J., Hospodor, A., Schwarz, T.: Redundancy management for P2P storage. In: Proc. of the Seventh IEEE Int. Symp. On Cluster Computing g and the Grid, CCGRID 2007, pp. 15–22. IEEE Computer Society, Washington, DC (2007).
[13] M. Blaum, J. Brady, J. Bruck, and J. Menon. EVENODD: An efficient scheme for tolerating double disk failures in RAID.
[14] L. Xu and J. Bruck. X-Code: MDS array codes with optimal encoding. IEEE Transactions on Information Theory, 45(1):272– 276, January 1999.
[15] I.S. Reed and G. Solomon: Polynomial Codes over Certain Finite Fields. Journal of the Society for Industrial and Applied Mathematics, June 1960.
[16] F.J. MacWilliams Holland Publishing Company, Amsterdam, New Applications. IEEE Press, New York, 1994. and N.J.A. Sloane. The Theory of Error- Correcting Codes, Part I. North-
[17] M. Luby, M. Mitzenmacher, A. Shokrollahi, D. Spielman, and V. Stemann. Practical loss-resilient codes. In 29th Annual ACM Symposium on Theory of Computing, pages 150–159, El Paso, TX, 1997. ACM. York, Oxford, 1977.
[18] W. W. Peterson and E. J. Weldon, Jr. ErrorCorrecting Codes, Second Edition. The MIT Press, Cambridge, Massachusetts, 1972.
[19] M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi, D. A. Spielman, and V. Stemann. Practical loss-resilient codes. In ACM symposium on Theory of Computing (STOC), 1997.
[20] M. Luby. LT codes. In IEEE Symposium on Foundations of Computer Science, 2002.
[21] Moritz Steiner, Taoufik En-Najjary, and Ernst W. Biersack. A global view of KAD. Proc. of Internet Measurement Conference (IMC), October 2007, San Diego, USA.